11.11. References 459
complete problems known as theHamiltonian Cycle Problem). But it turns out to
be easy to characterize which graphs have Euler tours.
Theorem.A connected graph has an Euler tour if and only if every vertex has even
degree.
(a)Show that if a graph has an Euler tour, then the degree of each of its vertices
is even.
In the remaining parts, we’ll work out the converse: if the degree of every vertex
of a connected finite graph is even, then it has an Euler tour. To do this, let’s define
an Eulerwalkto be a walk that includes each edgeat mostonce.
(b)Suppose that an Euler walk in a connected graph does not include every edge.
Explain why there must be an unincluded edge that is incident to a vertex on the
walk.
In the remaining parts, letwbe thelongestEuler walk in some finite, connected
graph.
(c)Show that ifwis a closed walk, then it must be an Euler tour.Hint:part (b)
(d)Explain why all the edges incident to the end ofwmust already be inw.(e)Show that if the end ofwwas not equal to the start ofw, then the degree of
the end would be odd.
Hint:part (d)
(f)Conclude that if every vertex of a finite, connected graph has even degree, then
it has an Euler tour.
Problems for Section 11.9
Class Problems
Problem 11.45.
Then-dimensionalhypercube,Hn, is a graph whose vertices are the binary strings
of lengthn. Two vertices are adjacent if and only if they differ in exactly 1 bit. For
example, inH 3 , vertices 111 and 011 are adjacent because they differ only in the
first bit, while vertices 101 and 011 are not adjacent because they differ at both
the first and second bits.
(a)Prove that it is impossible to find two spanning trees ofH 3 that do not share
some edge.