DEV Community

Samuel Kendrick
Samuel Kendrick

Posted on

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

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)
Enter fullscreen mode Exit fullscreen mode

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

        o (v0 = u)
        |
        o (v1)
        |
        o (v2)
        | 
        o (v3 = v)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)