Chapter 11 Simple Graphs424
Inductive step:
LetGebe the graph that results from removing an edge,e 2 E.G/. SoGe
haskedges, and by the induction hypothesisP.k/, we may assume thatGehas
at leastjV.G/j k-connected components. Now add back the edgeeto obtain
the original graphG. If the endpoints ofewere in the same connected component
ofGe, thenGhas the same sets of connected vertices asGe, soGhas at least
jV.G/j k >jV.G/j .kC1/components. Alternatively, if the endpoints of
ewere in different connected components ofGe, then these two components are
merged into one component inG, while all other components remain unchanged,
so thatGhas one fewer connected component thanGe. That is,Ghas at least
.jV.G/j k/ 1 DjV.G/j .kC1/connected components. So in either case,G
has at leastjV.G/j .kC1/components, as claimed.
This completes the inductive step and hence the entire proof by induction.
Corollary 11.9.8.Every connected graph withnvertices has at leastn 1 edges.
A couple of points about the proof of Theorem 11.9.7 are worth noticing. First,
we used induction on the number of edges in the graph. This is very common in
proofs involving graphs, as is induction on the number of vertices. When you’re
presented with a graph problem, these two approaches should be among the first
you consider.
The second point is more subtle. Notice that in the inductive step, we took an
arbitrary.kC1/-edge graph, threw out an edge so that we could apply the induction
assumption, and then put the edge back. You’ll see this shrink-down, grow-back
process very often in the inductive steps of proofs related to graphs. This might
seem like needless effort: why not start with ank-edge graph and add one more to
get an.kC1/-edge graph? That would work fine in this case, but opens the door
to a nasty logical error calledbuildup error, illustrated in Problem 11.48.
11.10 Forests & Trees
We’ve already made good use of digraphs without cycles, butsimplegraphs without
cycles are arguably the most important graphs in computer science.
11.10.1 Leaves, Parents & Children
Definition 11.10.1.An acyclic graph is called aforest. A connected acyclic graph
is called atree.
