11
$\begingroup$

Prove that every tree with $n\geq 2$ vertices has at least two vertices of degree one.

What I tried:

Suppose that there are fewer than two vertices of degree one. So we can split into two cases.

Case one: there is no vertex of degree one. Since we know that every tree has $n-1$ edges then the total degree of any tree have to be $2(n-1)$. But for this case since no vertex have degree $1$ then every vertex have at least a degree of $2$ and since there are $n$ vertices, the total degree is $\geq 2n$ which is a contradiction.

Case two: there is only one vertex of degree one. Similarly the total degree of any tree have to be $2(n-1)$. Then there are $(n-1)$ vertices with which have degree of $\geq 2$ while only one vertex with degree of one. Thus summing up to find the total of the vertices, we have that the total degree of vertices is $\geq 2(n-1)+1=2n-1$ which is also a contradiction.

This thus proves the statement for both cases.

Is my proof correct? Could anyone explain better?

$\endgroup$
0

4 Answers 4

7
$\begingroup$

Your proof is correct. Although, you could tighten it up a bit. Notice that your argument in case two is general enough to cover case one too. The heart of your argument could be boiled down to:

Every tree has $n-1$ edges, so the the sum of the degrees of all the vertices of any tree have to be $2(n-1).$ But if there are fewer than two vertices of degree one, then the sum of the degrees of all the vertices must be at least $2(n-1)+1,$ which is a contradiction.

$\endgroup$
2
$\begingroup$

Proposition: Any nontrivial tree must have at least two vertices of degree one (sometimes called leaves)

Here's a proof by contradiction:

Let $T$ be a nontrivial tree, that is, one with at least two vertices. In fact, let's draw one, just for fun:

        o (v1)
      /   \
(v0) o     o (v2)
         / 
        o (v3)

It might be easier to look at the tree like this:

        o (v0 = u)
        |
        o (v1)
        |
        o (v2)
        | 
        o (v3 = v)

Of note: I labeled $v_0$ as $u$ and $v_3$ as $v$. $u$ represents the beginning of the tree while $v$ represents the end.

Let $P$ be a path in $T$ of the longest possible length. It's alright if your tree has more than one path of equal length, so long as we choose one with the longest possible length. As mentioned above, $u$ and $v$ represent the beginning and end vertices of $P$. So our $P$ is $u, v_1, v_2, v$.

Next, suppose, contrary to the proposition, that there are NOT two vertices of degree one. This brings us to why we care about $P$. The longest path, in any tree, contains a start and end vertex of degree one.

Both ends of $P$ must be vertices with degree one, satisfying the "at least two vertices of degree one" part of the original proposition. But we're supposing that there are NOT two vertices of degree one.

That means either $u$ or $v$ need to be adjacent to one more vertex in $T$. Let's pick $u$, the start vertex and we will call the adjacent vertex $u'$.

Which vertex is $u'$? $u$ is already adjacent to a vertex on the path $P$ ($v_1$). If $u'$ was another vertex on the path $P$, then we'd get a cycle. I've illustrated this below:

        o (v0 = u)
      / |
     |  o (v1)
     |  |
      \ |
        o (v2 = u')
        | 
        o (v3 = v)

We cannot have cycles in a tree, since a tree is an undirected acyclic graph. So this can't be.

However, if we think $u'$ is a vertex adjacent to $u$, but not on the path $P$, then we will contradict our previous choice of $P$ as longest path since there would be a vertex preceding $u$.

$\endgroup$
1
$\begingroup$

Another way you can prove this is by saying is, as there are no cycles in a tree, there exists a longest path and the endpoints of the longest path must be with degree one. So there exista at least two vertices having degree one in a tree.

$\endgroup$
0
$\begingroup$

Looking at this from a Lakatos-esque viewpoint, the proof is correct, but the theorem is not. It's missing one key word.

Hint: what condition must we place on $n$ to ensure $2(n-1) < 2n-1$?

The proof only works for finite trees. There are infinite trees which have no vertices of degree one.

$\endgroup$
1
  • $\begingroup$ A worthwhile comment, but you are stating it as if correcting an error. Do you know what text the OP is using? As far as I know, the OP is working in a setting where all graphs are finite by definition. $\endgroup$
    – bof
    Nov 12, 2017 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.