11
$\begingroup$

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

Is this proof correct or am I missing the point?

  • 0
    @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.2010-12-12
  • 0
    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!2010-12-13
  • 0
    @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.2010-12-13

2 Answers 2

2

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?

  • 0
    Thanks for the hints. Basing on them I took another attempt at the proof.2010-12-13
  • 0
    Looking again I'm actually wrong. $\sum_{i \neq 1} d_i \neq 2(n - 2)$. I need to be more careful, too.2010-12-13
  • 0
    I had another idea, but it seems too simple to work. Please see my edit.2010-12-13
  • 0
    It does not work. It isn't necessarily true that $\sum_{i \neq n} d_i = 2(n-2)$.2010-12-13
  • 0
    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)?2010-12-13
  • 0
    As stated, $d_1, \ldots, d_n$ is fixed at the beginning of the problem.2010-12-13
  • 0
    Ok I give up on induction... If anyone is capable of presenting a proof I'd be very happy to see how it should look. Now, trying to make use of your original tip, we first have to prove that there exists a connected graph with degree sequence $d_i$ and then show that any connected graph with $n-1$ edges is a tree. Or the existence of connected graph is trivial and I just don't see it?2010-12-13
  • 1
    @George: Stick with the above ordering so $d_1 = 1$ and $d_n > 1$. Note that $d_2, \ldots, d_{n-1}, d_n - 1$ is a degree sequence of a tree by the inductive hypothesis. To that tree, add one vertex connected by one edge to the vertex with degree $d_n - 1$. The resulting graph is a tree, and has degree sequence $d_1, \ldots, d_n$. This completes your induction.2010-12-13
4

Hints for the other way round:

  • Do you know about mathematical induction?
  • Can every $d_i$ be $\gt 1$?
  • 0
    Thank you for the tips. I tried induction, please see my edited post.2010-12-13
  • 0
    @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...2010-12-13