Discrete Mathematical Structures by Pearson

Topics in Graph Theory 10-33

Step 2: Traverse any edge, choosing an edge that will disconnect the graph only if there is no

other choice.

Step 3: Repeat Step 2 until no edge remains in E.

END

Example:  Use Fleury’s algorithm on the graph to find an Eulerian circuit.

e

9

e

10

G

C

E

D

F

A

B

e

1

e

2

e

3

e

6

e

7

e

4

e

8

e

5

Solution: Each vertex is of even degree, and hence an Euler circuit is possible.

Step 1: We can start from any vertex. Let us start at the vertex A. We can traverse either edge

AB (i.e., e

1

) or AG (i.e., e

10

)

We choose AB. At B, there is only one edge BC (i.e., e

2

).

At C, we can choose either CD (i.e., e

3

) or CE. Let us choose CD. Proceeding step by step,