Discrete Mathematics for Computer Science

The K6nigsberg Bridge Problem 365

6.8.1 Graph Tracing

In directing a plotting device, commands are given to indicate where a pen should be

positioned to begin to draw a portion of the diagram and how the point of the pen should

move on the paper. When the pen is being repositioned to draw a different part of the

diagram, the write head is in the up position, or off the paper. If the diagram is composed

of many different parts, then a considerable amount of plotting time may be taken up with

repositioning the pen. It would be helpful to know ahead of time how many times the pen

must be repositioned and to schedule the plotting to use only as many pen motions in the

nondrawing position as are absolutely necessary.

An application of Euler's theorem is to determine whether all the edges of a graph can

be traced by a plotter exactly once, starting and ending at a given vertex. The next result

will answer the question about whether a graph could be drawn (passing over each edge

exactly once) without lifting the plotting pen. Figure 6.30 shows a graph that cannot be

drawn without lifting the pen.

128

13

G

Figure 6.30 A graph to plot.

Clearly, the pen could be lifted and repositioned for each edge in Figure 6.30. The real

question is this: What is the fewest number of times that a pen must be lifted to complete

the tracing of a graph? In particular, how many times must the pen be lifted to trace the

graph shown in Figure 6.30? (Assume that at the end of the plot, the pen is lifted so the

paper can be removed from the plotter but that this lifting is not counted when answering

the question.) Theorem 3 gives an answer to this question.

Theorem 2. Let G = (V, E) be a connected graph with 2 • k > 0 odd vertices for some

integer k. Then, there are k edge-disjoint trails

TrI, Tr2. Trk

in G such that

E(G) = E(Tr 1 ) U E(Tr 2 ) U ... U E(Trk)

Proof. Let V1, V2. V2.k-1, V2.k be the odd vertices of G where k > 0. Let H be the

graph formed from G by adding the k edges

(VI, V2), (V3, V4), " • " , (V2k-1, V2.k)
(You may be joining pairs of vertices that are already adjacent and need Euler's Theorem in
the context of multigraphs. As long as you allow the edge "set" of the graph to contain and
treat as different multiple edges joining the same pair of vertices, this proof is valid.) Every
vertex in H has even degree, so H has an Eulerian circuit. List the edges of an Eulerian
circuit of H beginning with the newly added edge (VI, v 2 ). Deleting the edge (vi, V2) from
the list results in a trail from v2 back to v1. Now, delete the added edge (v3, V4) from this
trail. The result will be two trails of the form v2 to v3 and v4 to vI or v2 to V4 and v3 to VI.