Eulerian and Hamiltonian Paths

Eulerian and Hamiltonian Paths and Circuits

Eulerian Paths and Circuits

An Eulerian path traverses every edge exactly once (vertices may be revisited).
An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

Conditions

If more than two vertices have odd degree, no Eulerian path exists.

Worked Example

Graph with vertices A, B, C, D, E and edges A–B, A–C, B–C, B–D, C–D, C–E, D–E.

Degrees: $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=4$, $\deg(D)=3$, $\deg(E)=2$.

Odd-degree vertices: B (3) and D (3). Exactly two — an Eulerian path exists from B to D (or D to B), but not a circuit.

Hamiltonian Paths and Circuits

A Hamiltonian path visits every vertex exactly once.
A Hamiltonian circuit visits every vertex exactly once and returns to the starting vertex.

Key Difference

Worked Example

A salesperson must visit 4 cities (A, B, C, D) and return to A. Connections exist: A–B, A–C, B–C, B–D, C–D.

Try: A → B → D → C → A. Check: visits A, B, D, C each once and returns to A. This is a valid Hamiltonian circuit.

Why These Matter

• Eulerian circuits: scheduling problems where every route (road, pipe, wire) must be covered exactly once — e.g., waste collection, snow ploughing.
• Hamiltonian circuits: travelling salesperson problems — visit each location once at minimum cost.

Quick Identification Guide

1. Count degrees of all vertices.
2. If all even → Eulerian circuit possible.
3. If exactly two odd → Eulerian path possible.
4. For Hamiltonian: look for a route visiting all vertices once and returning to start.

REMEMBER: Eulerian = Edges (every edge once). Hamiltonian = Houses/stops (every vertex once). The first letter helps you remember.

EXAM TIP: VCAA questions often show a graph and ask you to identify or describe an Eulerian or Hamiltonian path/circuit. Draw and label the route clearly, listing vertices in order.