Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is what I need to prove:

Let $d_1,d_2,...,d_n$ be a sequence of natural numbers (>0). Show that $d_i$ is a degree sequence of some tree if and only if $\sum d_i = 2(n-1)$.

I know that:
1. for any graph $\sum_{v \in V}\ deg(v) = 2e$;
2. for any tree $e=v-1$.
From 1 and 2 it follows that for any tree $\sum_{v \in V}\ deg(v) = 2(v-1)$.
If I understand it correctly, this is only a half of the proof ($\rightarrow$), isn't it? Any hints on how to prove it the other way?

Edit (induction attempt):

  1. $n=1$, we have $d_1 = 2(1-1) = 0$ and $d_1$ is a degree sequence of a tree.

  2. Let's assume the theorem holds for all $k<n$. So we know that $d_1 + d_2 + ... + d_{n-1} = 2(n-2) $ and that it's a degree sequence of a tree. In order to add one vertex to this tree, so that it remains a tree we only can add a vertex of degree one (we connect it to any existing vertex with a single edge). By doing this our new sequence is $1,d_1,...,d_j+1,...,d_{n-1}$, where $j$ is the vertex to which we attached the new vertex (it's degree increments). Clearly this sums to $2(n-1)$.

Is this proof correct or am I missing the point?

share|improve this question
    
@George: Yes, you understand correctly. You've shown that if $(d_1,\ldots,d_n)$ is a degree sequence of some tree, then $\sum d_i = 2(n-1)$. You still have to prove the other implication. –  Arturo Magidin Dec 12 '10 at 23:34
    
I think your induction attempt gets the point and is in the correct spirit, but you're assuming too much. You want to take an arbitrary graph with the degree sequence that has $\sum d_i = 2(n - 1)$. Do not assume it is a tree to begin with, you are trying to show this! –  Hans Parshall Dec 13 '10 at 1:01
    
Thanks Hans, I modified my proof. –  George Dec 13 '10 at 1:19
    
@George: the "otherwise" should read "sum to something bigger than or equal to $2n$". And you should add that you are adding another vertex and a single edge so that it remains a tree. You also need to show that you have a place to "attach" the new vertex, which means you need to be a bit more exlicit on what the "appropriately modified degree sequence" looks like. –  Arturo Magidin Dec 13 '10 at 1:27

2 Answers 2

up vote 2 down vote accepted

From your fact (1) and the hypothesis $\sum d_i = 2(n-1)$, you know $e = n - 1$. You need now only prove that any connected graph with $n - 1$ edges is a tree.

EDIT - Since you are going down an alternate path, I have a new suggestion.

Order the $d_i$ so that $d_1 \leq d_2 \leq \ldots \leq d_n$. Construct a tree with degree sequence $d_2, \ldots, d_n$. You know $\sum_{i \neq 1} d_i = 2(n - 2)$ (why?). Now try to construct your tree with degree sequence $d_1, \ldots, d_n$. You have to be careful about how you add in your vertex with degree $d_1$ so that it remains a tree, but this can be done.

EDIT - The above is incorrect. The idea remains to add in a vertex of degree $1$ to a tree with a specific degree sequence related to $d_1, \ldots, d_n$. But $\sum_{i \neq 1} d_i = 2n - 3$, so we cannot claim $d_2, \ldots, d_n$ is a degree sequence of a tree by the inductive hypothesis. Of course, when we add in the vertex of degree $1$, we alter the degree of another vertex, right?

share|improve this answer
    
Thanks for the hints. Basing on them I took another attempt at the proof. –  George Dec 13 '10 at 16:18
    
Looking again I'm actually wrong. $\sum_{i \neq 1} d_i \neq 2(n - 2)$. I need to be more careful, too. –  Hans Parshall Dec 13 '10 at 16:23
    
I had another idea, but it seems too simple to work. Please see my edit. –  George Dec 13 '10 at 16:53
    
It does not work. It isn't necessarily true that $\sum_{i \neq n} d_i = 2(n-2)$. –  Hans Parshall Dec 13 '10 at 17:00
    
Can't we get it from induction hypothesis - we assumed that theorem holds for all $k < n$ (so there exists $d_1,...,d_{n-1}$ such that its sum is $2(n-2)$ and the sequence is a degree sequence of some tree)? –  George Dec 13 '10 at 17:11

Hints for the other way round:

  • Do you know about mathematical induction?
  • Can every $d_i$ be $\gt 1$?
share|improve this answer
    
Thank you for the tips. I tried induction, please see my edited post. –  George Dec 13 '10 at 0:48
    
@George: You cannot say 'delete this vertex' as you haven't yet shown that it is the degree sequence of the tree (or a graph for that matter). But you can do something which modifies the degree sequence in a similar manner... –  Aryabhata Dec 13 '10 at 2:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.