Discrete Mathematics U.
Waterloo ECE 103, Spring 2010
Ashwin Nayak June 19, 2010
Some applications of graph theory
In these notes, we visit some important applications of elementary Graph Theory.
Gray Codes
An n-bit Gray code, also called the reflected binary code, is an ordering of the 2n strings of length n over {0, 1}
such that every pair of successive strings differ in exactly one position. For example, an 2-bit Gray code
is 00, 01, 11, 10, and a 3-bit Gray code is 000, 001, 101, 111, 011, 010, 110, 100.
If we use successive strings in a Gray code to represent the integers from 0 up to 2n − 1, instead of the usual
binary representation, we see that incrementing a number by one involves flipping only one bit. In the
usual binary representation, incrementing by 1 could lead to a sequence of bits that are carried over, which
may change several consecutive bits at once. For example, 7 + 1 = 8 in the usual binary representation
is 1112 + 12 = 10002, and we see that incrementing 111 by 1 causes four bits to be flipped. This simple
property makes Gray codes very useful in practice.
Although they had appeared in mathematical puzzles earlier, Gray codes were proposed in 1947 by Frank
Gray, a physicist and researcher at Bell Labs, to prevent spurious output from electromechanical switches.
(As you may have guessed, the codes are named after him.) Today, Gray codes are widely used to facilitate
error correction in digital communications such as digital terrestrial television and some cable TV systems.
We have seen Gray codes with 2 and 3 bits. Do they exist for all n? Below, we see that this question is
closely related to a basic property of the n-dimensional hypercube Hn .
Recall that the vertices of Hn are precisely the set of all n-bit strings, and two vertices x, y form an edge iff
they differ in exactly in one position. So, the question of existence of an n-bit Gray code may be reformu-
lated as: Is there a path in Hn that includes all the 2n vertices? The answer is, as you may have guessed,
yes! In fact, the hypercube satisfies a stronger property, that there is a cycle that contains all 2n of its vertices
(when n ≥ 2). Disregarding any one of the edges in such a cycle gives us the path we seek. Such a cycle is
shown in bold for H2 and H3 below; H1 cannot have such a cycle, but has the kind of path we seek.
0 1 0 1 1 0
0 1 1 1
1 1 1
0 1
0 1 1
1 0 0
0 0 0
1 0
0 0
2 0 0 1 1 0 1
Figure 1: Hamilton paths and cycles in H1 , H2 , H3 , depicted in bold.
Definition 1 A cycle in a graph G that contains all the vertices in it is called a Hamilton cycle (sometimes a
Hamiltonian cycle).
In the last home work, we saw that the grid graph Gn has a Hamilton cycle for even n. We now prove that
the n-hypercube also does, for all n ≥ 2. In proving this, we make use of the fact that we can construct
the (n + 1)-hypercube by connecting two copies of the n-hypercube with a suitable set of edges. So we can
1
construct a cycle in the larger hypercube by “cutting and pasting” cycles in the two copies. For example,
we obtained the Hamilton cycle in H3 shown above, by taking two cycles in the front and back faces (which
are isomorphic to H2 ), removing the edges {000, 010} and {001, 011} from the two cycles, and pasting them
with the edges {010, 011} and {000, 001}.
Theorem 2 For every integer n ≥ 2, the n-hypercube Hn has a Hamilton cycle.
Proof : The proof is by induction over n.
The base case is n = 2, and the statement is true, as H2 is isomorphic to C4 , the cycle on 4 vertices.
Assume, as our induction hypothesis, that the k-hypercube has a Hamilton cycle for some k ≥ 2. We prove
that the (k + 1)-hypercube also has a Hamilton cycle.
We partition the vertex set of Hk+1 into two sets V0 and V1 of equal size. The set V0 consists of all vertices
(i.e., (k + 1)-bit strings) beginning with a 0, and V1 consists of all vertices beginning with a 1:
n o
V0 = 0x : x ∈ {0, 1}k
n o
k
V1 = 1x : x ∈ {0, 1} .
Observe that the subgraph induced by either set V0 or V1 is isomorphic to Hk . By the induction hypoth-
esis, there is a cycle C0 = 0u1 , 0u2 , . . . , 0u2k , 0u1 that contains all the 2k vertices in V0 . Note that C1 =
1u1 , 1u2 , . . . , 1u2k , 1u1 is also a cycle, and it contains all the vertices in V1 .
We cut and paste C0 and C1 as follows: we delete the edges {0u2k , 0u1 } and {1u2k , 1u1 }, and insert edges {0u2k , 1u2k }
and {1u1 , 0u1 } to get the Hamilton cycle in Hk+1 :
0u1 , 0u2 , . . . , 0u2k , 1u2k , 1u2k −1 , . . . , 1u1 , 0u1 .
(Here, we have traversed the edges of the cycle C1 in reserve order.)
By mathematical induction, the statement is true for all n ≥ 2.
Euler tours
You may have come across this puzzle in your childhood: can you draw the pattern depicted in Figure 2 in
one stroke, without lifting your pencil off the paper, and without retracing any line? Of course, after trying
Figure 2: Can you draw this pattern without lifting your pencil off the paper, and without retracing any
line?
all different ways of tracing this pattern, we realize it is impossible. This puzzle is closely related to the
Seven Bridges of Königsberg problem, a historical problem in mathematics.
Much like the greater Montréal region formed on the St. Lawrence river, the city of Königsberg in Prussia
(now Kaliningrad, Russia) was set on both sides of the Pregel River. It included two large islands which
were connected to each other and the mainland by seven bridges (shown schematically in Figure 3).
2
Figure 3: Schematic map of Königsberg in the 1700s showing the Pregel river, its two islands, and the seven
bridges.
The problem was to find a walk through the city that would cross each bridge once and only once. The
islands could not be reached by any route other than the bridges, and every bridge was to be crossed
completely every time. One could not walk half way onto the bridge and then turn around and later cross
the other half from the other side.
Again, trying out all possibilities, we find that this task is impossible. In 1735, Leonhard Euler, the preem-
inent Swiss mathematician and physicist of the 18th century, explained this more generally by casting it in
terms of graphs, thereby founding a new field of study, graph theory. Euler’s solution was to represent the
two banks of the river Pregel, and the two islands by vertices, and the bridges by edges between these ver-
tices. Notice that this gives rise to multiple edges between pairs of vertices. The resulting object is therefore
called a multigraph, see Figure 4. Euler proved that if there were a solution to the seven bridges problem,
exactly two of the vertices would have odd degree, or all of them would have even degree. Since this is not
the case, there is no solution. Similarly, the puzzle in Figure 2 has no solution, as there are four odd degree
vertices.
Figure 4: The multigraph corresponding to the Königsberg bridges problem.
Below we study this kind of problem for general graphs. The results we prove also apply to multigraphs.
However, to avoid verifying which properties of graphs extend to multigraphs, and which do not, we
restrict ourselves to graphs. The puzzles above may be recast as graph problems by introducing new
vertices on the “extra” edges (see Figure 5), as can any other multigraph.
Definition 3 An Euler walk in a connected graph G (sometimes also called an Eulerian walk) is a walk in G that
traverses each edge exactly once. An Euler tour in a connected graph is a closed Euler walk, i.e., it starts and ends at
the same vertex in the graph.
The puzzles above ask us if there is an Euler walk in the (multi)graphs shown in Figure 5. Figure 6 shows
a graph with an Euler tour.
Theorem 4 Let G be a connected graph with at least two vertices. The graph G admits an Euler tour if and only if
all its vertices have even degree. The graph G admits an Euler walk if and only if it has exactly zero or two odd degree
vertices.
Proof : We show the theorem in three parts.
3
Figure 5: The multigraphs corresponding to the two puzzles. Multigraphs may be turned into graphs by
introduction of new vertices that “split” edges.
Figure 6: An Euler tour in the 2-dimensional Torus T3 . The solid black vertex is the start and the end of the
tour. The arrows on the edges show the direction in which the tour traverses them. The dashed lines show
which edge the tour follows, when there is more than one choice.
4
v
Figure 7: Constructing an Euler walk by splicing the path P (shown in bold) and a collection of
tours W1 , W2 , . . . , Wk . The dashed arrows show how the path and the tours are pasted together.
(a) Suppose the graph G has an Euler walk W . If the start and end vertices u, v of W are different, we show
that all vertices except u, v have even degree. If u = v (i.e., the walk is an Euler tour), then all vertices have
even degree.
Consider any vertex x other than u, v. Since the graph is connected and has more than one vertex, there is
some edge incident on x. Since W traverses all edges, it visits x as well. Each time W visits x, it traverses
two edges incident on it. Since W does not traverse any edge more than once, and traverses all edges, the
degree of x is even.
Similarly, every time W visits u or v after the start and before the end, it traverses two edges. At the start,
or at the end, it traverses only one edge. Therefore, if u 6= v, they have odd degree. Otherwise, they too
have even degree.
(b) Suppose the graph G has exactly two vertices u, v with odd degree. Then we show that it has an Euler
walk that starts at u and ends at v.
By the property shown in Quiz 9.2, there is a path P from u to v in G. If P is an Euler walk in G, we are
done. Otherwise, we remove the edges in P from G and any resulting vertices with degree 0. This leaves
us with a graph G′ with k connected components G1 , G2 , . . . , Gk , for some k ≥ 1. Each subgraph Gi is
connected, and has only even degree vertices (by Part (a)). Therefore, by the property in Part (c) we prove
below, it has an Euler tour Wi . We construct an Euler walk W by splicing P and Wi as follows.
Since G is connected, P has at least one (distinct) vertex xi in common with each Gi . Without loss of
generality, let the vertices xi occur in the order x1 , x2 , . . . , xk as we go from u to v in P . The walk W starts
at u and follows P up to x1 , then follows the Euler tour W1 of G1 , returns to x1 , then follows P to x2 , then
follows the Euler tour W2 of G2 , returns to x2 , and so on until all the subgraphs Gi have been toured, and
we are at xk . Then, we follow P to v, and we have our Euler walk. Note that since P is a path, and Wi are
Euler tours of disjoint components (that do not contain edges of P ), every edge is traversed exactly once.
This splicing is depicted in Figure 7. As shown in this figure, the path P may intersect a component in more
than one vertex.
(c) If all its vertices have even degree, then we show that G has an Euler tour.
The proof is by induction on the number of edges m in G. The base case is m = 3, since we are concerned
with simple graphs (that do not allow multiple edges). The graph then is isomorphic to C3 , the cycle on
three vertices, which has an Euler tour.
Assume, as induction hypothesis, that every connected graph with at most m edges, m ≥ 3, and only even
degree vertices has an Euler tour.
Consider a connected graph with m + 1 ≥ 4 edges with only even degree vertices. The graph G has at
least two vertices, as the number of edges is at least 4. By the property shown in Quiz 9.1, there is a
cycle C in G. If C is an Euler tour of G, we are done. Otherwise, as in the proof in Part (b), we remove
5
the edges in cycle C from G, along with any vertices that have degree 0 as a result. This leaves us with
components G1 , G2 , . . . , Gk , for some k ≥ 1, that have at least 2 vertices each, and only even degree vertices.
Moreover, each component has at most m edges as we removed all the edges of C, and C has at least three
edges. By the induction hypothesis, there is an Euler tour Wi in Gi . We splice together C with an arbitrary
start and end vertex u, and the tours Wi as in Part (b) above, to obtain an Euler tour of G.
This completes the proof of the theorem.
The Euler tour in Figure 6 was obtained by precisely the process which we have described in the above
proof.