Another useful special class of graphs:
Definition 5.5.1 A connected graph $G$ is a tree if it is acyclic, that is, it has no cycles. More generally, an acyclic graph is called a forest. $\square$
Two small examples of trees are shown in figure 5.1.5. Note that the definition implies that no tree has a loop or multiple edges.
Theorem 5.5.2 Every tree $T$ is bipartite.
Proof. Since $T$ has no cycles, it is true that every cycle of $T$ has even length. By corollary 5.4.3, $T$ is bipartite. $\qed$
Definition 5.5.3 A vertex of degree one is called a pendant vertex, and the edge incident to it is a pendant edge. $\square$
Theorem 5.5.4 Every tree on two or more vertices has at least one pendant vertex.
Proof. We prove the contrapositive. Suppose graph $G$ has no pendant vertices. Starting at any vertex $v$, follow a sequence of distinct edges until a vertex repeats; this is possible because the degree of every vertex is at least two, so upon arriving at a vertex for the first time it is always possible to leave the vertex on another edge. When a vertex repeats for the first time, we have discovered a cycle. $\qed$
This theorem often provides the key step in an induction proof, since removing a pendant vertex (and its pendant edge) leaves a smaller tree.
Proof. A tree on 1 vertex has 0 edges; this is the base case.
If $T$ is a tree on $n\ge 2$ vertices, it has a pendant vertex. Remove this vertex and its pendant edge to get a tree $T'$ on $n-1$ vertices. By the induction hypothesis, $T'$ has $n-2$ edges; thus $T$ has $n-1$ edges. $\qed$
Theorem 5.5.6 A tree with a vertex of degree $k\ge 1$ has at least $k$ pendant vertices. In particular, every tree on at least two vertices has at least two pendant vertices.
Proof. The case $k=1$ is obvious. Let $T$ be a tree with $n$ vertices, degree sequence $\ds\{d_i\}_{i=1}^n$, and a vertex of degree $k\ge2$, and let $l$ be the number of pendant vertices. Without loss of generality, $1=d_1=d_2=\cdots=d_l$ and $d_{l+1}=k$. Then $$2(n-1) = \sum_{i=1}^n d_i = l+k+\sum_{i=l+2}^n d_i \ge l+k+2(n-l-1).$$ This reduces to $l\ge k$, as desired.
If $T$ is a tree on two vertices, each of the vertices has degree 1. If $T$ has at least three vertices it must have a vertex of degree $k\ge 2$, since otherwise $2(n-1)=\sum_{i=1}^n d_i = n$, which implies $n=2$. Hence it has at least $k\ge2$ pendant vertices. $\qed$
Trees are quite useful in their own right, but also for the study of general graphs.
Definition 5.5.7 If $G$ is a connected graph on $n$ vertices, a spanning tree for $G$ is a subgraph of $G$ that is a tree on $n$ vertices. $\square$
Theorem 5.5.8 Every connected graph has a spanning tree.
Proof. By induction on the number of edges. If $G$ is connected and has zero edges, it is a single vertex, so $G$ is already a tree.
Now suppose $G$ has $m\ge1$ edges. If $G$ is a tree, it is its own spanning tree. Otherwise, $G$ contains a cycle; remove one edge of this cycle. The resulting graph $G'$ is still connected and has fewer edges, so it has a spanning tree; this is also a spanning tree for $G$. $\qed$
In general, spanning trees are not unique, that is, a graph may have many spanning trees. It is possible for some edges to be in every spanning tree even if there are multiple spanning trees. For example, any pendant edge must be in every spanning tree, as must any edge whose removal disconnects the graph (such an edge is called a bridge.)
Corollary 5.5.9 If $G$ is connected, it has at least $n-1$ edges; moreover, it has exactly $n-1$ edges if and only if it is a tree.
Proof. If $G$ is connected, it has a spanning tree, which has $n-1$ edges, all of which are edges of $G$.
If $G$ has $n-1$ edges, which must be the edges of its spanning tree, then $G$ is a tree. $\qed$
Theorem 5.5.10 $G$ is a tree if and only if there is a unique path between any two vertices.
Proof.
if: Since every two vertices are connected by a path, $G$ is connected. For a contradiction, suppose there is a cycle in $G$; then any two vertices on the cycle are connected by at least two distinct paths, a contradiction.
only if: If $G$ is a tree it is connected, so between any two vertices there is at least one path. For a contradiction, suppose there are two different paths from $v$ to $w$: $$v=v_1,v_2,\ldots,v_k=w \quad\hbox{and}\quad v=w_1,w_2,\ldots,w_l=w.$$ Let $i$ be the smallest integer such that $v_i\not= w_i$. Then let $j$ be the smallest integer greater than or equal to $i$ such that $w_j=v_m$ for some $m$, which must be at least $i$. (Since $w_l=v_k$, such an $m$ must exist.) Then $v_{i-1},v_i,\ldots,v_m=w_j,w_{j-1},\ldots,w_{i-1}=v_{i-1}$ is a cycle in $G$, a contradiction. See figure 5.5.1. $\qed$
Definition 5.5.11 A cutpoint in a connected graph $G$ is a vertex whose removal disconnects the graph. $\square$
Theorem 5.5.12 Every connected graph has a vertex that is not a cutpoint.
Proof. Remove a pendant vertex in a spanning tree for the graph. $\qed$
Exercises 5.5
Ex 5.5.1 Suppose that $G$ is a connected graph, and that every spanning tree contains edge $e$. Show that $e$ is a bridge.
Ex 5.5.2 Show that every edge in a tree is a bridge.
Ex 5.5.3 Show that $G$ is a tree if and only if it has no cycles and adding any new edge creates a graph with exactly one cycle.
Ex 5.5.4 Which trees have Euler walks?
Ex 5.5.5 Which trees have Hamilton paths?
Ex 5.5.6 Let $n\ge 2$. Show that there is a tree with degree sequence $d_1,d_2,\ldots,d_n$ if and only if $d_i>0$ for all $i$ and $\sum_{i=1}^n d_i=2(n-1)$.
Ex 5.5.7 A multitree is a multigraph whose condensation is a tree. Let $n\ge 2$. Let $d_1,d_2,\ldots,d_n$ be positive integers, and let $g$ be the greatest common divisor of the $d_i$. Show that there is a multitree with degree sequence $d_1,d_2,\ldots,d_n$ if and only if $\sum_{i=1}^n d_i/g\ge 2(n-1)$ and for some partition $I$, $J$ of $[n]$, $\sum_{i\in I}d_i=\sum_{i\in J} d_i$.
Ex 5.5.8 Suppose $T$ is a tree on $n$ vertices, $k$ of which have degree larger than 1, $d_1$, $d_2$,… $d_k$. Of course, $T$ must also have pendant vertices. How many pendant vertices? Your answer should depend only on $k$ and $d_1$, $d_2$,… $d_k$.