The Central Idea
Eulerian and Hamiltonian problems ask different questions.
An Eulerian problem asks:
\[ \boxed{\text{Can we use every edge exactly once?}} \]A Hamiltonian problem asks:
\[ \boxed{\text{Can we visit every vertex exactly once?}} \]Keeping this distinction clear is the first step in solving either type of problem.
Eulerian Problems Focus on Edges
In an Eulerian route, the primary restriction is on edges.
Every edge must be used exactly once.
Vertices may be visited more than once if necessary.
Hamiltonian Problems Focus on Vertices
In a Hamiltonian route, the primary restriction is on vertices.
Every vertex must be visited exactly once, apart from the permitted return to the starting vertex in a Hamiltonian cycle.
Not every edge needs to be used.
Euler Trail
An Euler trail is a trail that uses every edge of a graph exactly once.
\[ \boxed{\text{Euler trail}=\text{every edge exactly once}}. \]The starting and ending vertices may be different.
Euler Circuit
An Euler circuit is an Euler trail that begins and ends at the same vertex.
\[ \boxed{\text{Euler circuit}=\text{closed Euler trail}}. \]A connected graph with an Euler circuit is often called Eulerian.
A First Eulerian Example
Consider a cycle with four vertices:
\[ a-b-c-d-a. \]The route
\[ a,b,c,d,a \]uses every edge exactly once and returns to \(a\).
Therefore it is an Euler circuit.
Why Vertex Degree Matters
Suppose a route enters a vertex along one unused edge and later leaves along another unused edge.
The used edges naturally pair as
\[ \text{enter},\quad\text{leave}. \]This pairing explains why even and odd vertex degrees control Eulerian behavior.
Euler Circuit Criterion
A finite connected undirected graph has an Euler circuit if and only if every vertex has even degree.
\[ \boxed{ \text{Euler circuit} \iff \deg(v)\text{ is even for every vertex }v }. \]Isolated vertices may be ignored when discussing traversal of the nontrivial edge-containing part, but throughout this lesson we assume the relevant graph is connected.
Example: Euler Circuit by Degree
Suppose a connected graph has vertex degrees
\[ 2,\qquad4,\qquad2,\qquad4. \]Every degree is even.
Therefore the graph has an Euler circuit.
Euler Trail Criterion
A finite connected undirected graph has an Euler trail with different starting and ending vertices if and only if exactly two vertices have odd degree.
\[ \boxed{ \text{open Euler trail} \iff \text{exactly two vertices have odd degree} }. \]Endpoints of an Euler Trail
If exactly two vertices have odd degree, any Euler trail must begin at one odd-degree vertex and end at the other.
These two vertices are the only places where the enter-leave pairing can fail once.
Example: Open Euler Trail
Suppose a connected graph has degrees
\[ 3,\qquad2,\qquad2,\qquad1. \]Exactly two vertices have odd degree.
Therefore the graph has an Euler trail but no Euler circuit.
Too Many Odd-Degree Vertices
If a connected undirected graph has more than two odd-degree vertices, then it has neither an Euler circuit nor an Euler trail using every edge exactly once.
For example, four odd-degree vertices are already too many.
Why the Number of Odd-Degree Vertices Is Even
From the handshaking lemma,
\[ \sum_{v\in V}\deg(v)=2|E|. \]The degree sum is even.
Therefore the number of odd-degree vertices must itself be even.
This is consistent with the Eulerian cases:
\[ 0,\qquad2,\qquad4,\qquad6,\ldots \]Eulerian Classification Table
| Odd-Degree Vertices | Euler Trail? | Euler Circuit? |
|---|---|---|
| 0 | Yes | Yes |
| 2 | Yes | No |
| 4 or more | No | No |
Connectivity Still Matters
Even degree conditions are not enough by themselves if the graph is disconnected.
A route cannot traverse edges in one component and then move to another component without an edge connecting them.
Therefore connectivity must be checked before applying Eulerian degree tests.
Bridges and Eulerian Traversal
A bridge is an edge whose removal disconnects a graph.
During an Eulerian traversal, crossing a bridge too early can trap the route in a portion of the graph while unused edges remain elsewhere.
This observation leads to practical construction methods.
Fleury's Principle
A useful route-building principle is:
Do not cross a bridge unless there is no other unused edge available from the current vertex.
This principle underlies Fleury's algorithm for constructing Euler trails and circuits.
Euler's Königsberg Bridge Problem
The historical problem that helped launch graph theory asked whether a walker could cross each of seven bridges in Königsberg exactly once.
Euler represented land regions as vertices and bridges as edges.
The resulting graph had four odd-degree vertices, so no Euler trail was possible.
Hamiltonian Path
A Hamiltonian path is a path that visits every vertex of the graph exactly once.
\[ \boxed{\text{Hamiltonian path}=\text{every vertex exactly once}}. \]The path does not need to use every edge.
Hamiltonian Cycle
A Hamiltonian cycle visits every vertex exactly once and then returns to the starting vertex.
\[ \boxed{\text{Hamiltonian cycle}=\text{Hamiltonian path plus return to start}}. \]The starting vertex is repeated only to close the cycle.
A First Hamiltonian Example
Suppose a graph contains the cycle
\[ a,b,c,d,e,a \]and these are all the vertices of the graph.
Then the cycle is Hamiltonian because every vertex appears exactly once before returning to \(a\).
Unused Edges Are Allowed
A Hamiltonian cycle may ignore many edges.
The requirement concerns visiting vertices, not exhausting the entire edge set.
This is one of the sharpest differences from Eulerian traversal.
Eulerian versus Hamiltonian
| Feature | Eulerian | Hamiltonian |
|---|---|---|
| Main objects covered | Edges | Vertices |
| Must use every edge? | Yes | No |
| Must visit every vertex? | Usually reached as needed | Yes |
| May revisit vertices? | Yes | No, except start/end in cycle |
| Simple complete degree test? | Yes | No |
Hamiltonian Problems Are Harder to Characterize
For Eulerian problems, vertex degrees give a complete test in connected undirected graphs.
No comparably simple degree criterion completely characterizes Hamiltonian graphs.
Hamiltonian problems usually require structural reasoning, sufficient conditions, or systematic search.
A Necessary Degree Observation
If a graph has a Hamiltonian cycle, every vertex must have degree at least \(2\).
\[ \boxed{\deg(v)\ge 2\text{ for every vertex}} \]is therefore necessary.
But it is not sufficient: some graphs have minimum degree at least \(2\) and still have no Hamiltonian cycle.
Leaves Prevent Hamiltonian Cycles
A vertex of degree \(1\) cannot lie on a Hamiltonian cycle.
A cycle must enter and leave each vertex using two distinct incident edges.
Therefore, any graph with a leaf has no Hamiltonian cycle.
Leaves and Hamiltonian Paths
A Hamiltonian path can have vertices of degree \(1\), but such vertices must occur as endpoints of the path.
Therefore, if a connected graph has more than two leaves, it cannot have a Hamiltonian path.
Cut Vertices Can Cause Problems
A cut vertex is a vertex whose removal increases the number of connected components.
Strong bottlenecks created by cut vertices can prevent Hamiltonian cycles because a Hamiltonian cycle must pass through the graph without revisiting a vertex.
A Hamiltonian Cycle Cannot Have a Bridge
If a connected graph contains a bridge, then it cannot have a Hamiltonian cycle.
A Hamiltonian cycle would give an alternate route between the endpoints of every edge on the cycle, so no edge of that cycle could be a bridge.
Complete Graphs
A complete graph \(K_n\) connects every pair of distinct vertices.
For
\[ n\ge 3, \]every complete graph has a Hamiltonian cycle.
For example,
\[ v_1,v_2,\ldots,v_n,v_1 \]forms one.
Dirac's Theorem
A useful sufficient condition for Hamiltonicity is Dirac's theorem.
If a simple graph has \(n\ge3\) vertices and every vertex satisfies
\[ \deg(v)\ge\frac{n}{2}, \]then the graph has a Hamiltonian cycle.
This condition guarantees Hamiltonicity, but graphs failing the condition may still be Hamiltonian.
Necessary versus Sufficient Conditions
A necessary condition must hold whenever a structure exists.
A sufficient condition guarantees the structure when it holds.
For Hamiltonian cycles,
\[ \deg(v)\ge2 \]for every vertex is necessary, while Dirac's degree condition is sufficient.
Hamiltonian Search by Forced Choices
Structural constraints can force certain edges into a Hamiltonian route.
For example, if a vertex has degree \(2\) and a Hamiltonian cycle exists, then both of its incident edges must belong to that cycle.
Such forced choices can simplify the search.
Avoid Closing a Small Cycle Too Early
While constructing a Hamiltonian cycle, choosing edges that form a smaller cycle before all vertices are included usually makes completion impossible.
Once a vertex already has its two cycle edges, no additional cycle edge can pass through it.
Hamiltonian Problems and the Traveling Salesperson Problem
The traveling salesperson problem asks for a minimum-weight Hamiltonian cycle in a weighted graph, typically one representing travel costs or distances.
The Hamiltonian condition determines which tours are valid.
The weights determine which valid tour is best.
Eulerian Route Applications
Eulerian problems naturally arise when every connection or segment must be serviced.
- street sweeping;
- snowplow routing;
- garbage collection along streets;
- inspection of pipelines or cables;
- traversal of network links;
- drawing a figure without lifting a pen or retracing a segment.
Hamiltonian Route Applications
Hamiltonian problems arise when every location or state must be visited.
- delivery and tour planning;
- machine scheduling;
- genome and sequence problems;
- circuit design;
- state-space traversal;
- visit-each-location routing.
Directed Eulerian Problems
In a directed graph, an Euler circuit must follow edge directions.
For a strongly connected edge-containing digraph, a standard Euler-circuit condition is
\[ \boxed{\deg^+(v)=\deg^-(v)\text{ for every vertex }v}. \]Incoming and outgoing edge counts must balance at each vertex.
Directed Euler Trails
For an open directed Euler trail, the start vertex has one extra outgoing edge and the end vertex has one extra incoming edge:
\[ \deg^+(s)=\deg^-(s)+1, \] \[ \deg^-(t)=\deg^+(t)+1. \]All other vertices must have equal in-degree and out-degree, together with the appropriate connectivity condition.
Directed Hamiltonian Problems
A directed Hamiltonian path must follow arrow directions while visiting every vertex exactly once.
A directed Hamiltonian cycle must additionally return to the start along a directed edge.
As in undirected graphs, no simple complete degree criterion exists.
Common Error: Confusing Edges and Vertices
The most common mistake is reversing the two problem types.
Remember:
\[ \boxed{\text{Euler}\longrightarrow\text{edges}} \]and
\[ \boxed{\text{Hamilton}\longrightarrow\text{vertices}}. \]Common Error: Requiring Distinct Vertices in an Euler Trail
An Euler trail may revisit vertices.
It is the edges that may not repeat.
Common Error: Requiring Every Edge in a Hamiltonian Cycle
A Hamiltonian cycle only needs to visit every vertex.
Extra graph edges may remain completely unused.
Common Error: Ignoring Connectivity in Euler Problems
Even-degree vertices do not help if the edge-containing graph has separate components.
An Euler route must be able to move continuously through all edges.
Common Error: Treating Hamiltonian Degree Conditions as Exact Tests
Conditions such as Dirac's theorem are sufficient, not necessary.
A graph may fail Dirac's condition and still possess a Hamiltonian cycle.
A Reliable Procedure for Eulerian Problems
- Confirm the relevant graph is connected.
- Compute every vertex degree.
- Count the odd-degree vertices.
- If there are none, an Euler circuit exists.
- If there are exactly two, an open Euler trail exists between them.
- If there are more than two, no Euler trail using every edge exactly once exists.
- When constructing the route, avoid using a bridge prematurely when alternatives remain.
A Reliable Procedure for Hamiltonian Problems
- Decide whether a Hamiltonian path or cycle is required.
- Look for obvious obstructions such as leaves or bridges.
- Use degree information to identify forced edges or impossible vertices.
- Do not close a smaller cycle before all vertices are included.
- Track visited vertices carefully.
- Use sufficient theorems when their hypotheses apply.
- If no structural shortcut applies, search systematically through plausible routes.
Example: Full Eulerian Classification
Suppose a connected graph has degrees
\[ 4,\qquad2,\qquad3,\qquad3,\qquad2. \]Exactly two vertices have odd degree.
Therefore the graph has an Euler trail whose endpoints are those two odd-degree vertices.
It does not have an Euler circuit.
Example: Hamiltonian Obstruction
Suppose a connected graph has three leaves.
Each leaf could only appear as an endpoint of a Hamiltonian path.
But a path has only two endpoints.
Therefore,
\[ \boxed{\text{the graph has no Hamiltonian path}}. \]Practice 1: Euler or Hamilton?
A problem asks for a route that uses every street exactly once.
Is this Eulerian or Hamiltonian?
Practice 2: Euler Circuit
A connected graph has degrees
\[ 2,\qquad4,\qquad4,\qquad2. \]Does it have an Euler circuit?
Practice 3: Euler Trail
A connected graph has degrees
\[ 1,\qquad2,\qquad4,\qquad3. \]Does it have an Euler trail?
Practice 4: Too Many Odd Vertices
A connected graph has four odd-degree vertices.
Can it have an Euler trail using every edge exactly once?
Practice 5: Hamiltonian Path
What must a Hamiltonian path do with the vertices of the graph?
Practice 6: Leaf Obstruction
A graph has a vertex of degree \(1\).
Can the graph have a Hamiltonian cycle?
Practice 7: Multiple Leaves
A connected graph has four leaves.
Can it have a Hamiltonian path?
Practice 8: Dirac's Condition
A simple graph has \(10\) vertices, and every vertex has degree at least \(5\).
What does Dirac's theorem guarantee?
Practice 9: Directed Euler Circuit
In a strongly connected digraph, every vertex has equal in-degree and out-degree.
What Eulerian conclusion follows?
Practice 10: Identify the Error
A student says, “This graph has an Euler circuit because I found a cycle that visits every vertex once.”
Explain the error.
Practice Answers
Practice 1
The requirement concerns using every edge exactly once.
\[ \boxed{\text{Eulerian}}. \]Practice 2
Every degree is even, and the graph is connected.
\[ \boxed{\text{Yes, an Euler circuit exists.}} \]Practice 3
The odd degrees are \(1\) and \(3\), so exactly two vertices have odd degree.
\[ \boxed{\text{Yes, an open Euler trail exists.}} \]Practice 4
More than two odd-degree vertices prevent an Euler trail using every edge exactly once.
\[ \boxed{\text{No}}. \]Practice 5
A Hamiltonian path must visit
\[ \boxed{\text{every vertex exactly once}}. \]Practice 6
No. A Hamiltonian cycle must enter and leave every vertex using two incident cycle edges.
\[ \boxed{\text{A degree-1 vertex prevents a Hamiltonian cycle.}} \]Practice 7
Every leaf would have to be an endpoint of the Hamiltonian path, but a path has only two endpoints.
\[ \boxed{\text{No Hamiltonian path exists.}} \]Practice 8
Since
\[ \frac{n}{2}=\frac{10}{2}=5, \]every vertex satisfies Dirac's condition.
\[ \boxed{\text{The graph has a Hamiltonian cycle.}} \]Practice 9
Equal in-degree and out-degree at every vertex, together with the stated connectivity, gives
\[ \boxed{\text{a directed Euler circuit}}. \]Practice 10
Visiting every vertex once describes a Hamiltonian cycle, not necessarily an Euler circuit.
To be Eulerian, the route must use
\[ \boxed{\text{every edge exactly once}}. \]What to Remember
- Eulerian problems concern edges.
- Hamiltonian problems concern vertices.
- An Euler trail uses every edge exactly once.
- An Euler circuit is a closed Euler trail.
- A connected undirected graph has an Euler circuit exactly when every vertex has even degree.
- A connected undirected graph has an open Euler trail exactly when two vertices have odd degree.
- A Hamiltonian path visits every vertex exactly once.
- A Hamiltonian cycle visits every vertex exactly once and returns to the start.
- No simple degree test completely characterizes Hamiltonian graphs.
- Leaves, bridges, cut structures, and degree conditions can provide useful Hamiltonian obstructions or guarantees.
Where We Go Next
Eulerian and Hamiltonian problems study global traversal through a graph. Other problems ask whether a graph can be drawn or labeled under structural restrictions.
The next lesson, Planarity and Graph Coloring, studies drawings without edge crossings and assignments of colors that separate adjacent objects.