Show that every non-increasing sequence $(d_1, d_2, . . . , d_n)$ of positive integers $\sum_{i=1}^nd_i =2(n-1)$ is a degree sequence of a tree.
I was thinking induction..$(n-1)=e(G)$ b/c connected graph is a tree
graph theorytrees
Show that every non-increasing sequence $(d_1, d_2, . . . , d_n)$ of positive integers $\sum_{i=1}^nd_i =2(n-1)$ is a degree sequence of a tree.
I was thinking induction..$(n-1)=e(G)$ b/c connected graph is a tree
Best Answer
Examples are almost always easier to understand than generalizations.
So, whenever you are confused in math, write down a simple example.
The formula $\sum_{i=1}^{n}d_i =2(n-1)$ is quite ugly.
Suppose that $n = 3$
Now, the formula $\sum_{i=1}^{n}\mathtt{STUFF}\quad$ becomes $d_1 + d_2 + d_3 = 4$.
If one of the three nodes was free-floating then the graph would not be a tree.
So, put $1$ in for each of $d_1, d_2, d_3$ to get $(1, 1, 1)$
The sum of $(1, 1, 1)$ is $3$, not $4$
If we were putting pigeons in holes (houses) then we would have one pigeon left-over.
$3$ out of $4$ pigeons have been stuffed into birdhouses. One pigeon remains.
The sequence can never increase as you go from left to right.
As such, the pigeon must go into the left-most house.
$(2, 1, 1)$ is the final degree sequence.
I have embedded a picture below:
Suppose that $n = 5$
Now, the formula $\sum_{i=1}^{n}\mathtt{STUFF}\quad$ becomes $d_1 + d_2 + \dots + d_5 = 8$.
As said earlier, if you had a free-floating dot (node or vertex) then the graph would not be a tree.
So, put $1$ in for each of $d_1, d_2, \dots, d_5$ to get $(1, 1, 1, 1, 1)$
The sum of $(1, \dots, 1)$ is $5$, not $8$.
$5$ out of $8$ pigeons have been stuffed into birdhouses. $3$ pigeons remain.
The sequence can never increase as you go from left to right.
As such, the $6^{\text{th}}$ pigeon must go into the left-most bird-house.
$(2, 1, 1, 1, 1)$ is our degree sequence so far.
$2$ pigeons remain homeless.
The final possible non-increasing degree sequences for 5 vertices are:
It would be sufficient to prove the following lemma:
DEFINITION OF THE HAPPY LEMMA
That is not quite right, because you have to be careful if $d^{\prime}(a) = 0$
As an examples of a "merger" of two sequences consider (3, 2) and (5, 4, 1).
attach the two sequences end-to-end and then sort the elements so that the resulting sequence is non-decreasing
$\mathtt{MERGE}[(3, 2), (5, 4, 1)] = (5, 4, 3, 2, 1)$
The following definitions make things more confusing, but you might want to include them for purposes of rigor:
Basically, the proof would looks something like this:
Defintion of special:
EDIT:
You will be almost done if you can show that for every non-increasing sequence $D = (d_1, d_2, . . . , d_n)$ of positive integers having $\sum_{i=1}^nd_i =2(n-2)$ there exist two trees such that $D$ is the degree sequence of the disjoint union of the two trees.
Your original formula was $\sum_{i=1}^nd_i =2(n-1)$ The new formula is $\sum_{i=1}^nd_i =2(n-2)$