Trees

Theorem 6

The following definitions are equivalent:

$G$ is a tree (connected without cycle).
For every two vertices $u,v$ , there exists exactly one path from $u$ to $v$ .
The graph $G$ is connected and deleting any edge disconnects the graph.
Graph $G$ has no cycle and adding any edge into $G$ creates a cycle.
$G$ is connected and $|E| = |V|-1$ .

In these lecture notes, we will show the equivalence between (1) and (5). The other equivalences are left as an exercise. A leaf of a tree is a vertex of degree one. The following two lemmas will give us a natural way to do induction on a tree.

Lemma 4 (Leaf lemma)

If $G$ is connected without cycle and $|V(G)| \ge 2$ , then $G$ contains at least two different leaves.

This is again one of those intuitively true statements. No matter how you try to draw it, it is true. But this is not a proof, since there are infinitely many trees, whereas proofs are finite.

Proof:

Take $P=(v_1,\ldots, v_q)$ to be a path of maximum length in $G$ . Note that $q \ge 2$ . We claim that $v_1$ and $v_q$ are both leaves (do you see why they are different?). Assume otherwise that $\deg(v_1) > 1$ (the other case is similar). Then there is an edge $(u,v_1)$ where $u \neq v_2$ . If $u$ appears on $P$ , i.e., $u=v_i$ for $i >2$ , $(v_1,v_2,\ldots, v_i, v_1)$ would be a cycle, which is a contradiction. Otherwise, if $u$ is not on $P$ , then the path $(u,v_1,\ldots, v_q)$ is a path longer than $P$ , a contradiction since $P$ is a longest path.

Lemma 5 (Tree growing lemma)

Let $v$ be a leaf of $G$ . The following statements are equivalent: (i) $G$ is a tree and (ii) $G-v$ is a tree.

Proof:

To prove (i) $\implies$ (ii), assume that $G$ is a tree, and we argue that $G-v$ is connected (the fact that $G-v$ does not have a cycle is even simpler!). Look at $G-v$ and take two vertices $u,w$ in $G-v$ (and thus none of those is $v$ ). Since $G$ is connected, there exists a path connecting $u$ and $w$ in $G$ . This path cannot contain $v$ since the degree of $v$ is one. Therefore, this is a path in $G-v$ . Since every $u$ and $v$ are connected via a path, the graph $G-v$ is connected.

To prove (ii) $\implies$ (i), assume that $G-v$ is a tree. Graph $G$ cannot have a cycle that involves $v$ (since $v$ has degree one), so we only need to check that $G$ is connected. Every pair of vertices $u,w$ in $G-v$ is connected in $G-v$ . Moreover, $v$ is connected to every $w$ in $G-v$ since we can first connect $v$ to $v' \in V(G-v)$ via an edge and from $v'$ to $w$ due to the connectedness of $G-v$ .

Notice that these lemmas are quite simple to prove, but they require some effort (especially the mental effort to resist the "proof by picture" temptation). Whenever we claim that a cycle exists, the proof explicitly shows a sequence of vertices that form a cycle. Whenever we claim connectedness, we explicitly identify a sequence of vertices on paths that connect pairs of vertices. Now we are ready to show the proof of the theorem.

Proof (Equivalence (1)

\iff

(5)):

We prove this by induction on the number of vertices. The induction hypothesis (IH): For all $n \geq 1$ , $G$ is a tree if and only if $G$ is connected and $|E| = |V|-1$ . The base case when $n=1$ is trivial. Now assume that the IH is true for $n_0$ and consider a graph with $n_0+1$ vertices. To prove (1) $\implies$ (5), we need to argue that $|E(G)| = |V(G)|-1$ . From the previous two lemmas, there exists a leaf vertex $v$ in $G$ so that $G- v$ is a tree. We know, from IH, that $|E(G-v)| = |V(G-v)| -1$ and this implies that $|E(G)| = |V(G)| -1$ .

To prove the converse, assume that $|E(G)| = |V(G)|-1$ . First we argue that there exists a leaf in $G$ (do you see why we cannot just use the leaf lemma we already proved?). By connectedness, every vertex in $G$ has degree at least one. By the Handshake's lemma, we have $\sum_{v \in V(G)} \deg(v) = 2|E(G)| = 2(|V(G)|-1)$ . So there must be at least two vertices of degree one. Take $v$ to be a leaf of $G$ . Notice that $G-v$ is connected and satisfies $|E(G-v)| = |V(G-v)| -1$ , so by IH, we know that $G-v$ contains no cycle. Since $v$ has degree one, a cycle in $G$ cannot contain $v$ , so $G$ cannot have any cycle.

Notice that a nice property about trees is the inductive property we use above ( $G$ is a tree if and only if $G-v$ is a tree, when $v$ is a leaf). Trees are a very important objects in computer science and have played fundamental roles in almost every area of algorithm design.

Exercise 19

Complete the proof of Theorem 6.

Exercise 20

Draw all trees on the vertex set $V = \{1,2,3,4\}$ and all pairwise non-isomorphic trees.

Exercise 21

Let $G$ be a tree with $|V(G)| \ge 2$ . Prove:

$p_1 = 2+ \sum_{d \geq 3} (d-2) p_d$

where $p_d$ denotes the number of vertices in $G$ having degree $d$ .

Notice that the above exercise provides an alternative proof of the Leaf lemma.