loading...

Any tree with at least two vertices must have at least two vertices of degree one.

adnauseum profile image Samuel Kendrick ・2 min read

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)

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

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

Of note: I labeled v0 as u and v_3 as v. More on that later.

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 start and finish vertices of P. So our P is u, v1, v2, 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 (v1). 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.

Discussion

markdown guide