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. U
No wonder the people of K6nigsberg could not find a good walk: Every vertex of the
graph in Figure 6.26 is odd!
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. U
No wonder the people of K6nigsberg could not find a good walk: Every vertex of the
graph in Figure 6.26 is odd!