트리의 차수 시퀀스 인 양의 정수 시퀀스.
허락하다 $k\geq 2$ 과 $T$ 나무가되다 $k$정점. 허락하다$ D_k = (d_1,\cdots, d_k)$양의 정수 시퀀스입니다. 보여줘$D_k$ 도 순서 $T$ iff $\sum_{i=1}^k d_i = 2k-2.$
포워드 시사점을 위해 우리는 $2|E(T)| = 2(k-1) = 2k-2 = \sum_{i=1}^k d_i$.
반대의 의미를 위해 $\sum_{i=1}^k d_i = 2k-2.$ 우리는 그것을 보여주고 싶습니다 $(d_1,\cdots, d_k)$ 도 순서 $k.$ 우리는 $k.$ 에 대한 $k=2,$ 우리는 $d_1 + d_2 = 2.$ 둘 다 이후 $d_1$ 과 $d_2$ 양의 정수, $d_1 = 1 = d_2,$ 그래서 $(d_1, d_2)$ 나무의 차수 순서 $k$정점. 따라서 기본 케이스가 유지됩니다. 이제 모두를 위해$2\leq k < m, m\geq 3, $ 할때는 언제나 $(d_1,\cdots, d_k)$ 양의 정수 시퀀스이므로 $\sum_{i=1}^k d_i = 2k-2,$ $(d_1,\cdots, d_k)$ 나무의 정도 순서입니다. $k$정점. 허락하다$D_{m} = (d_1,\cdots, d_{m})$ 일련의 $m$ 양의 정수로 $\sum_{i=1}^m d_i = 2m-2.$ 하나라면 $d_i = 2,$ 그때 $D_m[i] := (d_1,\cdots, d_{i-1}, d_{i+1},\cdots, d_m)$ 일련의 $m - 1$ 양의 정수 $\sum_{1\leq j\leq n, j\neq i} d_j = 2m-4 = 2(m-1) - 2.$ 따라서 귀납적 가설에 의해 $D_m[i]$ 나무의 차수 순서 $T_{m-1}$ 의 위에 $m-1$정점. 이후$m-1\geq 2, T_{m-1}$ 적어도 $1$ 잎 $t_1$. 새 정점 추가$t'$ ...에 $T_{m-1}$ 그래서 $t_1 t'$ 가장자리이고하자 $T_{m-1}'$결과 트리가됩니다. 그때$T_{m-1}'$ 그래프입니다 $m$ 두 나무의 차수 시퀀스 간의 유일한 차이점은 $T_{m-1}'$ 학위가 하나 더 있습니다 $2$. 우리는$T_{m-1}'$나무입니다. 그것이 있는지 관찰하십시오$m-1$ 가장자리, 이후 $T_{m-1}$ 있다 $m-2$ 가장자리 및 두 정점 $u \neq t', v \neq t'\in V(T_{m-1}')$ 경로가있다 $T_{m-1}'\backslash t' = T_{m-1}$ ...에서 $u$ ...에 $v$. 또한 이웃을 추가 할 수 있습니다.$t', t_1,$ 경로의 시작으로 $t_1$ 다른 정점에 $t_1$ 과 $t'$ ($t'$ 과 $t_1$정의에 따라 경로로 연결되므로이 두 가지와 구별되는 정점 만 고려하면됩니다. 그래서$T_{m-1}'$연결되어 있으므로 나무입니다. 그러므로,$(d_1,\cdots, d_m)$ 나무의 차수 순서 $T_{m-1}'.$
그러나, 나는 그렇지 않은 경우를 처리하는 데 많은 어려움을 겪고 있습니다. $d_i=2$, 그리고 나는 그것을 완전히 증명할 수 없습니다. 더 간단한 접근 방식이 있습니까?
답변
나에게 발생하는 귀납 주장은 조금 다릅니다. 결과가 다음보다 짧은 모든 시퀀스에 대해 참이라고 가정합니다.$k$ 정리의 조건을 충족하고 $D_k=\langle d_1,\ldots,d_k\rangle$ 다음과 같은 양의 정수 시퀀스 $\sum_{i=1}^kd_i=2k-2$.
아이디어는 모든 $1$ 시퀀스의 용어를 사용하므로 $D_k$ 정말 나무의 정도 순서입니다. $T$, 펜던트 정점을 제거합니다. 물론 이것은 펜던트 정점의 수만큼 나머지 정점의 총 정도를 감소시킬 것이므로 나머지 항을 조정해야합니다.$D_k$ 총 금액만큼 아래로 $1$자귀. 비결은 정리의 조건을 만족하는 더 짧은 시퀀스를 얻을 수있는 방식으로이를 수행하여, 유도 가설을 적용하여 트리를 얻는 것입니다.$T'$ 그런 다음에 적절한 잎을 추가하여 나무를 얻습니다. $T$ 학위 순서는 $D_k$, 유도가 완료되었습니다.
만약 $d_i\ge 2$ ...에 대한 $i=1\ldots,k$, 다음 $\sum_{i=1}^kd_i\ge 2k$, 불가능하므로 하나 이상의 $i$ 그런 $d_i=1$. (사실 적어도 두 개가 있습니다.) 우리는$d_1\le d_2\le\ldots\le d_k$. 허락하다$\ell=\max\{i\in[k]:d_i=1\}$; 그때
$$\sum_{i=\ell+1}^kd_i=2k-2-\ell=\big(2(k-\ell)-2\big)+\ell\,.$$
만약 $\ell=k$, 다음 $k=\sum_{i=1}^k1=2k-2$, 그래서 $k=2$, 및 $\langle 1,1\rangle$ 실제로 나무의 정도 순서입니다. $2$정점; 그렇지 않으면$\sum_{i=\ell+1}^kd_i\ge\ell$.
만약 $\sum_{i=\ell+1}^kd_i=\ell$, 다음 $2k-2=2\ell$, 그래서 $\ell=k-1$, 그리고 우리는 나무의 차수 순서를 가지고 있습니다. $K_{1,k-1}$. 그렇지 않으면,$\sum_{i=\ell+1}^kd_i>\ell$. 과
$$\sum_{i=\ell+1}^k(d_i-1)=2k-2-\ell-(k-\ell)=k-2\,,$$
그래서 $k-2>\ell-(k-\ell)$, $2k-2>2\ell$, $k-1>\ell$, 및 $\sum_{i=\ell+1}^k(d_i-1)\ge\ell$.
허락하다 $m$ 최대가되어 $\sum_{i=\ell+1}^m(d_i-1)\le\ell$. 에 대한$i=1\ldots,m-\ell$ 허락하다 $d_i'=1$, 그리고 $m<k$ 허락하다 $d_{m-\ell+1}'=\sum_{i=\ell+1}^{m+1}(d_i-1)-\ell+d_{m+1}$. 만약$m+1<k$ 허락하다 $d_i'=d_{\ell+i}$ ...에 대한 $i=m-\ell+2,\ldots,k-\ell$. 그때
$$\sum_{i=1}^{k-\ell}d_i'=\sum_{i=1}^kd_i-2\ell=2(k-\ell)-2\,,$$
그래서 귀납 가설에 의해 $\langle d_1',\ldots,d_{k-\ell}'\rangle$ 나무의 차수 순서 $T'$ 의 위에 $k-\ell$정점. 의 정점을 보자$T'$ 있다 $\{v_1,\ldots,v_{k-\ell}\}$, 그리고 $d(v_i)=d_i'$ ...에 대한 $i=1,\ldots,k-\ell$. 에 대한$i=1,\ldots,m-\ell$ 붙이다 $d_{\ell+i}-1$ 에 잎 $v_i$, 첨부 $\ell-\sum_{i=\ell+1}^m(d_i-1)$ 에 잎 $v_{m-\ell+1}$, 해당 정점이 존재하는 경우. 결과 트리는$k$ 정점 및 차수 시퀀스 $\langle d_1,\ldots,d_k\rangle$.