Chapter 9 Directed graphs & Partial Orders348
(b)Give an example of a digraph in which a vertexvis on an odd-length closed
walk but not on an odd-length cycle.
(c)Prove that every odd-length closed walk contains a vertex that is on an odd-
length cycle.
Problem 9.7. (a)Give an example of a digraph that has a closed walk including
two vertices but has no cycle including those vertices.
(b)Prove Lemma 9.2.6:
Lemma.The shortest positive length closed walk through a vertex is a cycle.
Problem 9.8.
AnEuler tour^15 of a graph is a closed walk that includes every edge exactly once.
Such walks are named after the famous 17th century mathematician Leonhard Eu-
ler. (Same Euler as for the constante2:718and the totient function —he did
a lot of stuff.)
So how do you tell in general whether a graph has an Euler tour? At first glance
this may seem like a daunting problem (the similar sounding problem of finding
a cycle that touches every vertex exactly once is one of those million dollar NP-
complete problems known as theHamiltonian Cycle Problem)—but it turns out to
be easy.
(a)Show that if a graph has an Euler tour, then the in-degree of each vertex equals
its out-degree.
A digraph isweakly connectedif there is a “path” between any two vertices that
may follow edges backwards or forwards.^16 In the remaining parts, we’ll work out
the converse. Suppose a graph is weakly connected, and the in-degree of every
vertex equals its out-degree. We will show that the graph has an Euler tour.
Atrailis a walk in which each edge occursat mostonce.
(b)Suppose that a trail in a weakly connected graph does not include every edge.
(^15) In some other texts, this is called anEuler circuit.
(^16) More precisely, a graphGis weakly connected iff there is a path from any vertex to any other
vertex in the graphHwith
V.H/DV.G/;and
E.H/DE.G/[fhv!uijhu!vi 2 E.G/g:
In other wordsHDG[G ^1.