Euler and Hamilton Paths/Circuits

Euler Path (EDGES)

A path that includes every edge just one.

To locate an Euler path all vertices MUST be of even degree, or there must be exactly two vertices of ODD degree, if it is the latter then you will start at one odd degree and finish at the other odd degree.

Euler Path

Essential Further Mathematics 4ed 2012 (page 626)

The Euler path for the above graph is: B, A, E, D, B, C, D, C.

NOTE: You can have repeated vertices in an Euler path, because you are going through the path once.

Euler Circuit (EDGES)

An Euler circuit has paths which travels through every edge once, and goes back to the start again. That is, you start and finish at the same vertex.

In order to locate an Euler circuit, check to see if all the vertices are of even degrees.

Euler Circuit

Essential Further Mathematics 4ed 2012 (page 626)

The Euler circuit in the above graph is: C, D, E, C, A, B, C

Hamilton Path (VERTICES)

Hamilton paths only pass through every vertex ONCE. Therefore, you don’t need to travel through all the edges.

Hamilton Path

Essential Further Mathematics 4ed 2012 (Q’s 3 p.628)

A possible Hamilton path for the above graph is: F, E, D, A, B, C, H, G.

 

Hamilton Circuits (VERTICES)

 

Every vertex in the graph is visited ONCE and you return back to the same vertex that you started at. (Start and finish at the same vertex, after visiting every vertex).

Hamilton Circuit

Essential Further Mathematics 4ed 2012 (Q’s 2(c) p.628)

A Hamilton circuit for the above graph: A, B, D, C, E, A.