Discrete Mathematics for Computer Science

366 CHAPTER 6 Graph Theory

After deleting the remaining edges that were added to G to form H, k edge-disjoint trails

containing all the edges of G are formed. 0

Corollary 1: Let G be connected and have two vertices of odd degree. There is a Euleria

trail in G that begins at one of the odd vertices and ends at the other.

For the proof of Corollary 1, it is possible that the pair of odd vertices to which you

add an extra edge are already connected. Keeping track of such an edge as separate from

the one originally in the graph is all that is needed to make the proof valid.

For any decomposition of a graph into pairwise edge disjoint trails, each vertex of odd

degree must be the end of at least one trail. Therefore, since each trail has two ends, a

graph with 2 • k odd vertices with k > 0 cannot be decomposed into fewer than k trails.

In terms of the plotting problem, interpret this result to say that the pen will have to be

lifted and moved at least k - 1 times if the plot graph contains 2 .k vertices of odd degree

where k > 0. For the graph shown in Figure 6.30, it would be necessary to lift the pen once,

because there are four vertices of odd degree. The two part tracing of the graph shown in

Figure 6.31 accomplishes the tracing while lifting the pen a minimum number of times.

End

18 12 7

Start End^1

Start

Figure 6.31 Minimum tracing of a graph.

Figure 6.32 shows other possible trail decompositions of the graph shown in Figure

6.30. Theorem 3 mentions nothing about the uniqueness of the decomposition. Each dif-

ferent way of adding edges to pairs of odd vertices may give a different set of trails.

1 2 12 12

3 4•91 6 9 0 5 661

Tri^13 Tr

6 12

30 Tr 2

5 1

Tr 2 13

Figure 6.32 Other trail decompositions.