Advanced High-School Mathematics

SECTION 2.2 Elementary Graph Theory 113

Theorem. (Euler’s Degree Theorem)The sum of the degrees of the
vertices equals twice the number of edges in the graph.

As a result, one has

Corollary. The number of vertices of odd degree must be an even
number.

The above results arenegative in the sense that they tell us when
it’s impossible to construct Eulerian circuits or Eulerian trails. We
shall give an algorithm which allows us to find an Eulerian circuit in a
graph all of whose degrees are even.

Fleury’s algorithm for finding an Eulerian circuit

Assume that we are given the graphGall of whose vertex degrees are
even. In tracing a trail inG, after having traveled along an edgeE, we
shall remove this edge (we have “burned our bridges behind us”).

Step 1. Pick a vertexX.

Step 2. Move from X to an adjacent vertex Y along the edge E

unless removingEdisconnectes the graph. (There may be several

choices. Also, if there is only one choice, you need to take this

choice!)

Step n. Return finally toX.

The above algorithm is depicted in the following sequence. The
dotted edges represent the removed edges.