Prove that trees have at least two vertices of degree one

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?

Solution 1:

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.

Solution 2:

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

Solution 3:

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.