Discrete Mathematics for Computer Science

362 CHAPTER 6 Graph Theory

be difficult, but it would require that the terminology of multigraphs be explained. The

notions are obvious extensions of the ideas used with graphs and can be formulated by the

reader. The main point is to treat the multiple edges as distinct entities in the set of edges

rather than as multiple listings of the same element in a set. Euler's theorem will be proved

for graphs as defined in Section 6.1.1.

By trial and error, it will become clear that no circuit in the graph shown in Figure

6.26 starts and ends at the same vertex and contains each edge once. Hence, no walk of the

required kind exists in K6nigsberg. When there is a circuit (trail) in a graph that includes

each edge exactly once, the circuit (trail) is called an Eulerian circuit (trail). Euler's

theorem gives necessary and sufficient conditions for the existence of an Eulerian circuit

in a graph.

Theorem 1. (Kiinigsberg Bridge Theorem) (Euler, 1736) Let G be a connected

graph. G has an Eulerian circuit if and only if each vertex is even.

Proof. (=:) Let G be a graph that has an Eulerian circuit C, and show that every vertex

of G is even.

Let C be v 1 , V2. Vn where a vertex vi for 1 < i < n may occur more than once in

the list. We want to show that each vertex vi has even degree.

Before continuing the proof, we consider an example that motivates how this part of

the proof will go.

Motivation for the proof: In Figure 6.27, the circuit

C = 1,2, 3, 1,4,5, 1,6,7,8,6,2,9, 1

with the edges

(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)

is an Eulerian circuit. In Figure 6.27, you can follow the Euler circuit by traversing the

edges by going from vertex to vertex in the following order: 1-2-3-1-4-5-1-6-7-8-6-2-9-1.

3

2 2

4

8

6

~ 5

SStart

7

Figure 6.27 Graph with an Eulerian circuit.

For each of the vertices 2, 3 ... , 9, we can see that each time the vertex occurs as the

end of an edge, it is the beginning of the next edge. Thus, each time one of these vertices

occurs in the circuit, we can add 2 to the running total of the degree of that vertex. For the

vertex 1, the same computation works for all its occurrences except for the first and the last

in the circuit. Both the first and the last occurrence of vertex 1 contribute one to the degree