Discrete Mathematics for Computer Science

The Kbnigsberg Bridge Problem 363

of vertex 1 so there is an addition of two to the degree of vertex 1 for these occurrences. A
summary for these calculations is given in Table 6.2.

Table 6.2 Computing Degrees in Traversing an Euler Circuit

Traversal of an Euler Circuit

Add to Current Total-i1 When Entering a Vertex and 1 When Leaving a Vertex-

Table shows running totals

Euler Circuit (1,2)(2,3)(3,1)(1,4)(4,5)(5,1)(1,6)(6,7)(7,8)(8,6)(6,2)(2,9)(9,1)

Vertex Start 1- 2- 3- 1- 4- 5- 1- 6- 7- 8- 6- 2- 9- 1 Degree

1 0 1 3 5 6 6

2 0 2 4 4

3 0 2 2

4 0 2 2

5 0 2 2

6 0 2 4 4

7 0 2 2

8 0 2 2

9 0 2 2

Continuation of the proof: First, consider the case where v 0 xl; then, also, v = x,.
Vertex vi occurs in C some number t of times. In each case, there are edges in G from vi

to the preceding and succeeding vertices of G-two edges per occurrence of vi. Moreover,

no edge is allowed to occur twice in the circuit, so in all, there are 2t edges incident to vi.

If v = xl, then the argument is analogous, except that one pair of edges is (Xl, X2) and

(Xn-1, X0).

(4=) Conversely, suppose that every vertex of a connected graph G has even degree, and
prove that G contains an Eulerian circuit. Select a vertex v in G, and begin a trail T at v.
Continue this trail as long as possible until a vertex w is encountered that has all the edges

incident to it in T. To prove that a circuit has been formed, show that v = w. Suppose

v 5 w. Each time w is encountered on T, except for the last time, one edge is used to enter

w and another to leave w. The last time w is encountered in T, only one edge is used-the

one to enter w. Therefore, an odd number of edges incident to w occur in T. Since the
degree of w is even, there must be at least one edge incident with w that does not belong
to T. Therefore, T can be continued, which is a contradiction, and so w = v. If T contains
all the edges of G, then T is an Eulerian circuit of G.
Before continuing the proof, we consider an example that motivates how the rest of
this proof will go.

Motivation for the proof: Suppose the circuit T does not contain all the edges of G.
An example of such an occurrence is shown in Figure 6.28. (This graph is known as Mo-
hammed's Scimitar.)