Chapter 11 Simple Graphs458
[h]N
F
T
P ⊕ Q
P
Q
XOR
b F
a
c
d
e
Figure 11.32 A 3-colorXOR-gateProblems for Section 11.8
Homework Problems
Problem 11.43. (a)Give an example of a simple graph that has two verticesu¤v
and two distinct paths betweenuandv, but no cycle including eitheruorv.
(b)Prove that if there are different paths between two vertices in a simple graph,
then the graph has a cycle.
Problem 11.44.
The entire field of graph theory began when Euler asked whether the seven bridges
of Konigsberg could all be crossed exactly once. Abstractly, we can represent the ̈
parts of the city separated by rivers as vertices and the bridges as edges between
the vertices. Then Euler’s question asks whether there is a closed walk through the
graph that includes every edge in a graph exactly once. In his honor, such a walk is
called anEuler tour.
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 Millenium Prize NP-