364 CHAPTER 6 Graph Theory
12 8
3 69
4 10
G(^1 8 8)
1*2 7
(^36 39) 4° •- 010
51 90
(^4 5 11)
T u H
Figure 6.28 Circuit that is not Eulerian.
Continuation of the proof: Define H to be the spanning subgraph of G with edge set
E(G) - E(T). Since every vertex in T has even degree, every vertex in H has as degree
a value that is the difference of two even numbers and, hence, is an even number. Choose
an edge (u, v) that is in H and that has at least one endpoint, v, in T. Such a choice is
possible because G is connected. Let H 1 be the connected component of H that contains
the vertex v.
Begin a trail U at v in H1, and continue it as long as possible. As before, U will end at
its starting vertex v and be a circuit. Now, form a circuit C in G that has more edges than T
by inserting U at v. The larger circuit is formed when v is reached while traveling around
T, by taking a side trip around U (splicing U to T) before completing the rest of T.Motivation for the proof. An example of this operation is shown in Figure 6.29.
Start for U
1 2 7 8 1 8
3 6 9
5 1110 4 5 110
/ H
Start for T
T:4-3-2-6-7-8-9-10-11-5-4 U:2-1-3-5-6-11-9-7-2
t
Splice vertex
Spliced Circuit: C:4-3-2-1-3-5-6-1 1-9-7-2-6-7-8-9-10-11-5-4
Figure 6.29 Splicing circuits.Continuation of the proof: If T now contains all the edges of G, then T is an Eulerian
circuit. If T still does not contain all the edges of G, then form the spanning subgraph with
edge set E(G) - E(T), and repeat the process outlined for U to find a circuit in this graph
that can be spliced onto T. Repeat this process until an Eulerian circuit for G is formed. UNo wonder the people of K6nigsberg could not find a good walk: Every vertex of the
graph in Figure 6.26 is odd!