Proving Non-Trivial Trees Have At Least 2 Vertices with Degree <2

[Reshma]

I'm not sure where to post this, but anyway here is the question:

Given a graph G(p,q) is a tree where p is the number of vertices and q is the number of edges.

Since given graph is a tree, number of edges q=p-1.

How do you prove that every non-trivial tree has atleast two vertices with degree less than 2?

P.S.: A tree is a connected acyclic graph.

 

[shmoe]

Sum up the degrees of the vertices in two ways, once as a sum over the vertices and once as a sum over the edges. Assume you don't have two vertices with degree one, use this assumption to get a lower bound for the sum of the degrees and you'll find a contradiction.

 

[Reshma]

Thanks for replying.

Here is my proof:
Graph G(p,q) is a tree. Hence q=p-1.
Let us assume that the tree does not have any vertices with degree 1.
Let d_i represent degree of any vertex i ranging from 1 to p.

We know \sum d_i = 2q
\sum d_i = 2p-2

How do you get a lower bound on this and get a contradiction?

 

[Reshma]

Can someone help?

 

[shmoe]

Well if you assumed you had no vertices of degree 1, then each d_i must be greater than or equal to what number? What does this say about \sum d_i, keeping in mind that p is the number of vertices?

Can we modify this slightly to rule out the possiblity of only one vertex of degree 1? What about 2 vertices of degree 1, is this possible?

 

[Reshma]

OK,based on the assumption--each d_i is greater than or equal to 2.

How do you now prove there are atleast 2 verices of degree 1?

 

[shmoe]

OK,based on the assumption--each d_i is greater than or equal to 2.

You're adding up p things, each of which is at least 2, so \sum d_i \geq ?

 

[Reshma]

Ok, so \sum d_i \geq 2p...which is a contradiction.
Hence there are atleast 2 vertices of degree 1.

Thank you.

 

[shmoe]

Hang on, this lower bound of 2p came from the assumption that we had no vertices of degree 1, so this contradiction only tells you that you have at least one vertex of degree 1. The point of this cse was to give you a (slightly) simpler version to try first.

What inequality do you get if you assume you have only one vertex of degree 1? You should get a similar contradiction.

 

[Reshma]

I'm sorry, I cannot arrive at any contradiction
can you help?

 

[shmoe]

Let's make the indicies explicit. You know:

\sum_{i=1}^{p}d_i=2p-2

Now suppose you have 1 vertex with degree 1, the rest two or more. Without loss of generality assume d_p=1 and d_i\geq 2 for all 1<=i<p. Using this, what is a lower bound for the sum?

 

[Reshma]

The lower bound is: \sum d_i \geq 2p+1
Right? This also a contradiction. Hence there has to be atleast 2 verices of degree 1.

Hope I got it right this time.

 

[shmoe]

Why the +1?

break the sum up:

\sum_{i=1}^{p}d_i=d_p+\sum_{i=1}^{p-1}d_i

and use my assumption above that the pth vertex was the only one with degree 1, the rest (all p-1 of them) have degree 2 or more..

 

[Reshma]

\sum_{i=1}^{p}d_i=d_p+\sum_{i=1}^{p-1}d_i

\sum_{i=1}^{p}d_i=2p-2

d_p=1

\sum_{i=1}^{p-1}d_i\geq 2(p-1)
--->right?

 

[shmoe]

--->right?

Good, now combine everything.

 

[mathwonk]

use induction on the number of edges. It is true if there is only one edge.

Now just collapse any edge, collapsing vertex a to vertex b. The result is true for the new graph by induction. If collapsing the edge changed the degree of b from 2 to one, it is obvious that either b or a also had degree one originally.


done.

moral: induction is a ridiculously powerful tool.

 

[Reshma]

Good, now combine everything.

\sum_{i=1}^{p}d_i=d_p+\sum_{i=1}^{p-1}d_i
Hence, 2p-2 = 1 + [2(p-1)]_{min}

You get an absurd equation. Hence a contradiction.

 

[mathwonk]

what do you think of the inductive argument? doesn't it seem easier?

 

[Reshma]

what do you think of the inductive argument? doesn't it seem easier?

No, I find the inductive aurgument pretty difficult to understand. Sorry

 

[mathwonk]

let me try to explain it more clearly:

we wish to show that a non trivial finite tree has at least two vertices of degree one, i.e. from which there emanate only one edge. We will argue by induction on the number n of edges.

By definition, a non trivial tree has at least one edge. So we begin the induction with the case n=1. Then it is clear that both vertices have exactly one edge and we are done.

Now assume the result for all graphs with n-1 edges, and let us consider a graph G with n ≥ 2 edges.

Choose any edge e at all, with endpoints a and b, and collapse e to a point.

This produces a new graph G' with n-1 edges. The two endpoints a and b of e have been combined together into one new vertex called c.

Now let's compute the degree of c. I claim deg(c) = deg(a) + deg(b) -2.

I.e. all edges, except for e, that used to end at either a or b now end at c, so we must add them. (Since G was a tree, only one edge, namely e, ended at both a and b, so a and b had no edges in common except for e.) Since the missing edge e counted as one for both deg(a) and deg(b), we must subtract it twice have our formula. i.e. deg(c) = deg(a)-1 + deg(b)-1.

Now deg(c) cannot be zero, since that would mean that G had only the one edge e.

Consequently, deg(c) ≥ 1, and if deg(c) =1, then either deg(a) or deg(b)=1.

All other vertices of G' have the same degree they had in G, since they fail to meet e.

Now by the inductive hypothesis, there are two vertices say x,y, of G' of degree one. If neither of these is c, we are done, since our collapsing process did not affect them, so the same two vertices on G also had degree one.

If it happens that say x = c, then deg(c) =1, so either a or b had degree 1 in G, say deg(a) = 1. Then in G we had at least two vertices of degree one, namely a and y.

Does this seem clearer?

 

[mathwonk]

come on guys. surely you can respond to this.

 

[Reshma]

Collapsing edges? Does this mean you deleting a vertex or an edge?

 

[shmoe]

come on guys. surely you can respond to this.

Not much for me to say about it. Personally I think arguing by the sum of the degrees of vertices is simpler and it uses more of the given information (q=p-1). This isn't to say induction proofs aren't very valuable in graph theory though! Both should be understood.


Reshma, "collapsing an edge" means removing that edge from the graph and identifying its two vertices as one. For example, if you collapse the edge in the tree with two vertices, you get the tree with one vertex.

 

[Reshma]

This discussion on graph theory has been quite insightful for me. Thank you very much, Shmoe for your cooperation and Mathwonk too!

 

[mathwonk]

well simplicity is in the eye of the beholder but if you go back now and re read my original 2 sentence proof in #16, I think it is about as simple as possible. No formulas are needed, the argument took me about 10 seconds to think of, and completely settles the matter.

 

[shmoe]

I didn't at all mean to imply that the induction method here isn't groovy. I liked the other way for it's emphasis on how restrictive a condition like q=p-1 can be and the joys of counting the same thing twice. Which is simpler or nicer is definitely in the eye of the beholder.

I'm sure all beholders would agree that both basic techniques, counting the same thing in two different ways and induction, are key tools in both graph theory (and combinatorics)?

 

[mathwonk]

i just like arguments i can do in my head in a few seconds, with no computation.