Proving the degree sequence of 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:

BINARY TREE HAVING ONE ROOT AND TWO LEAVES

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:

  • $(4, 1, 1, 1, 1)$
  • $(3, 2, 1, 1, 1)$
  • $(2, 2, 2, 1, 1)$

PICTURE OF STAR WITH FOUR LEAVES AND ONE ROOT

JPEG picture of a path of 5 nodes

It would be sufficient to prove the following lemma:

DEFINITION OF THE HAPPY LEMMA

Let $d$ be a special sequence.

$\forall a,b \in \mathbb{N}$ if $a \neq b$ and if $a,b \leq$ the last valid index of $d$ and if $d^{\prime}$ is a sequence almost the same as $d$ except that $d^{\prime}(a) = d(a) - 1$ and $d^{\prime}(b) = d(b) - 1$ then $d^{\prime}$ is the merger of two special sequences shorter than $d^{\prime}$.

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:

In the statement of the happy lemma, we talk about two sequences being almost the same. any two sequences $d$ and $d^{\prime}$ "almost the same" if and only if when $n$ is the length of $d$ then $d^{\prime}$ is a mapping from $\{k \in \mathbb{N}: 1 \leq k \leq n\}$ to $\mathbb{N}$ then $\forall x \in \{k \in \mathbb{N}: 1 \leq k \leq n\}/\{a, b\}$ $d^{\prime}(x) = d(x)$

For any two sequences, $S$ and $T$ the merger of the two sequences is a sequence $R$ such that $R$ is non-increasing and there exists a permutation $P$ of the indicies of the concatenation of $S$ and $T$ such that for all indices $k$ of the concatenation of $S$ and $T$, $R(P(k))$ is equal to the $k^{\text{th}}$ element of the concatenation of $S$ and $T$

Basically, the proof would looks something like this:

We proceed by induction.

In the base case, for each special sequence $S$ of length $1$, $2$, or $3$ there exists at least one tree whose degree sequence is $S$

Let $n \in \mathbb{N}$

Assume that for every special sequence of length $n$ or smaller, there exists at least one tree having that sequence as the degree sequence of the tree.

Let $d$ be a special sequence of length $n + 1$
There definitely exists a graph having degree sequence $d$.
It remains to show that there exists a tree having degree sequence $d$.
Let $G$ be a graph having degree degree sequence $d$.
delete any edge from graph $G$ to form graph $G^{\prime}$
Let $d^{\prime}$ be the degree sequence of $G^{\prime}$
Then, there exist $a,b \in \{k \in \mathbb{N}: k \leq n\}$ such that $a \neq b$ and $d^{\prime}(a) = d(a) - 1$ and $d^{\prime}(b) = d(b) - 1$.

By the happy lemma, $d^{\prime}$ is the sum of two special sequences each of length $n$ or less. Let the two shorter sequences be known as $\mathtt{LEFT}\text{ }\mathtt{SEQUENCE}$ and $\mathtt{RIGHT}\text{ }\mathtt{SEQUENCE}$ By the inductive hypothesis, there exists a tree for $\mathtt{LEFT}\text{ }\mathtt{SEQUNCE}$ and there exists a tree blah, blah, blah ... When you put an edge between the two trees, you get a new tree which has degree sequence $d$

Defintion of special:

Any sequence $d$ is special if and only if $\sum_{i=1}^{\mathtt{LEN}(d)}d_i =2(\mathtt{LEN}(d)-1)$ and $d$ is non-decreasing.

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)$

Related Question