Chapter 11 Simple Graphs330
is a closed walk starting and ending atu, and its length is
jwujCjwvjC1:
This length is odd, sincewuandwvare both even length or are both odd
length.
3 IMPLIES 1 Proof. Since there is an odd length closed walk, the WOP implies
there is a odd length closed walkwof minimum length. We claimwmust be
a cycle. To show this, assume to the contrary that there is vertexxthat ap-
pears twice on the walk, sowconsists of a closed walk fromxtoxfollowed
by another such walk. That is,
wDfbxr
for some positive length walksfandrthat begin and end atx. Since
jwjDjfjCjrj
is odd, exactly one offandgmust have odd length, and that one will be an
odd length closed walk shorter thanw, a contradiction.
This completes the proof of Theorem 11.10.1.
Theorem 11.10.1 turns out to be useful since bipartite graphs come up fairly often
in practice. We’ll see examples when we talk about planar graphs in Chapter 12.
11.11 Forests & Trees
We’ve already made good use of digraphs without cycles, butsimplegraphs without
are arguably the most important graphs of all in computer science.
11.11.1 Leaves, Parents & Children
Definition 11.11.1.An acyclic graph is called aforest. A connected acyclic graph
is called atree.
The graph shown in Figure 11.18 is a forest. Each of its connected components
is by definition a tree.
One of the first things you will notice about trees is that they tend to have a lot
of nodes with degree one. Such nodes are calledleaves.
