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

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.

Definition 5.5.3 A vertex of degree one is called a **pendant**
vertex,
and the edge incident to it is a pendant edge.

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.

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.

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.

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.

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

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.

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.

Definition 5.5.11 A **cutpoint** in a connected graph $G$
is a vertex whose removal disconnects the graph.

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.

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