11.11. Forests & Trees 333
edge is removed, no path remains, and so the graph is not connected.- Since the tree has at least two vertices, the longest path in the tree will have
different endpointsuandv. There cannot be an edge from an endpoint to
any other vertex on the path, because that would form a cycle. There also
can’t be an edge from an endpoint to any vertex not on the path, because that
make a longer path. So both endpoints must be leaves. - We use induction on the proposition
P.n/WWDthere aren 1 edges in anyn-vertex tree:Base case(nD 1 ):P.1/is true since a tree with 1 node has 0 edges and
1 1 D 0.Inductive step: Now suppose thatP.n/is true and consider an.nC1/-vertex
tree,T. Letvbe a leaf of the tree. You can verify that deleting a vertex of
degree 1 (and its incident edge) from any connected graph leaves a connected
subgraph. So by Theorem 11.11.3.1, deletingvand its incident edge gives
a smaller tree, and this smaller tree hasn 1 edges by induction. If we re-
attach the vertex,v, and its incident edge, we find thatThasnD.nC1/ 1
edges. Hence,P.nC1/is true, and the induction proof is complete. Various subsets of properties in Theorem 11.11.3 provide alternative characteri-
zations of trees. For example,
Lemma 11.11.4.A graphGis a tree iffGis a forest andjV.G/jDjE.G/jC 1.
We’ll leave the proof as an exercise.11.11.3 Spanning Trees
Trees are everywhere. In fact, every connected graph contains a subgraph that is
a tree with the same vertices as the graph. This is a called aspanning treefor
the graph. For example, Figure 11.22 is a connected graph with a spanning tree
highlighted.
Theorem 11.11.5.Every connected graph contains a spanning tree.
Proof. SupposeGis a connected graph. Define aspanning subgraphofGto be
a subgraph in which every pair of vertices ofGare connected. Because the graph
Gis connected,Gitself is a spanning subgraph. So by WOP, there must be a