¡@

An Introduction to Euler Paths and Circuits

¡@

Let¡¦s look at the graph below:

¡@

circuit.gif (1358 bytes)

¡@

¡@

A vertex in an intersection of 2 edges.  An edge is an arc joining any 2 vertices.

¡@

Euler path:

A graph is said to be containing an Euler path if it can be traced in 1 sweep without lifting the pencil from the paper and without tracing the same edge more than once. Vertices may be passed through more than once. The starting and ending points need not be the same.

¡@

¡@

Euler circuit:

An Euler circuit is similar to an Euler path, except that the starting and ending points must be the same.

¡@

Let¡¦s look at the graphs below; do they contain an Euler circuit or an Euler path?

¡@

          graph1.gif (1830 bytes)            graph2.gif (1548 bytes)            

                       Graph 1                                          Graph 2                         

graph3.gif (1216 bytes)                 graph4.gif (1398 bytes)      

Graph 3                                             Graph 4

graph5.gif (1744 bytes)                             graph6.gif (1796 bytes)

    Graph 5                                                 Graph 6

What is the relationship between the nature of the vertices and the kind of path/circuit that the graph contains? We¡¦ll have the answer after looking at the table below.

¡@

¡@

Graph

Number of odd vertices (vertices connected to an odd number of edges)

Number of even vertices (vertices connected to an even number of edges)

What does the path contain?

(Euler path = P;

Euler circuit = C;

Neither = N)

1

0

10

C

2

0

6

C

3

2

6

P

4

2

4

P

5

4

1

N

6

8

0

N

¡@

¡@

From the above table, we can observe that:

¡@

  1. A graph with all vertices being even contains an Euler circuit.
  2. A graph with 2 odd vertices and some even vertices contains an Euler path.
  3. A graph with more than 2 odd vertices does not contain any Euler path or circuit.

The 7 bridges of Konigsberg ~ Finding an Euler circuit

Back to main page

¡@

¡@

¡@