142 8. Trees
will still not contain a cycle (while adding a new edge may create a cycle).
The following theorem shows that trees can be characterized as “minimally
connected” graphs as well as “maximally cycle-free” graphs.
Theorem 8.1.1(a) A graphGis a tree if and only if it is connected, but
deleting any of its edges results in a disconnected graph.
(b) A graphGis a tree if and only if it contains no cycles, but adding
any new edge creates a cycle.
Proof. We prove part (a) of this theorem; the proof of part (b) is left as
an exercise.
First, we have to prove that ifGis a tree then it satisfies the condition
given in the theorem. It is clear thatGis connected (by the definition of
a tree). We want to prove that if we delete any edge, it cannot remain
connected. The proof is indirect: Assume that when the edgeuvis deleted
from a treeG, the remaining graphG′is connected. ThenG′contains a
pathPconnectinguandv. But then, if we put the edgeuvback, the path
Pand the edgeuvwill form a cycle inG, which contradicts the definition
of trees.
Second, we have to prove that ifGsatisfies the condition given in the
theorem, then it is a tree. It is clear thatGis connected, so we only have
to argue thatGdoes not contain a cycle. Again by an indirect argument,
assume thatGdoes contain a cycleC. Then deleting any edge ofC,weob-
tain a connected graph (Exercise 7.2.5). But this contradicts the condition
in the theorem.
Consider a connected graphGonnnodes, and an edgeeofG.Ifwe
deletee, the remaining graph may or may not remain connected. If it is
disconnected, then we calleacut-edge. Part (a) of Theorem 8.1.1 implies
that every edge of a tree is a cut-edge.
If we find an edge that is not a cut-edge, delete it. Go on deleting edges
until a graph is obtained that is still connected, but deleting any edge from
it leaves a disconnected graph. By part (a) of Theorem 8.1.1, this is a tree,
with the same node set asG. A subgraph ofGwith the same node set that
is a tree is called aspanning treeofG. The edge deletion process above
can, of course, be carried out in many ways, so a connected graph can have
many different spanning trees.
Rooted trees.Often, we use trees that have a special node, which we call
theroot. For example, trees that occurred in counting subsets or permuta-
tions were built starting with a given node.
We can take any tree, select any of its nodes, and call it a root. A tree
with a specified root is called arooted tree.
LetGbe a rooted tree with rootr. Given any nodevdifferent fromr,
we know from Exercise 8.1.3 below that the tree contains a unique path
connectingvtor. The node on this path next tovis called thefatherof