Euler and Hamilton paths are graph theory ideas used to study routes through networks. This cheat sheet helps students tell the difference between visiting every edge and visiting every vertex. It is useful for contest math, discrete math, computer science, and real-world routing problems.
The main goal is to quickly decide which type of path or cycle may exist in a graph.
An Euler path uses every edge exactly once, while a Hamilton path visits every vertex exactly once. Euler problems often have clear degree rules, especially for connected graphs. Hamilton problems are harder because there is no simple test that works for every graph.
Key tools include vertex degree, connectedness, complete graphs, and careful checking for repeated edges or vertices.
Key Facts
- An Euler path in a connected graph exists exactly when the graph has or vertices of odd degree.
- An Euler circuit in a connected graph exists exactly when every vertex has even degree.
- If a connected graph has exactly odd-degree vertices, every Euler path must start at one odd vertex and end at the other.
- A Hamilton path visits every vertex exactly once, but it does not need to use every edge.
- A Hamilton cycle visits every vertex exactly once and returns to the starting vertex, so the start vertex is repeated only at the end.
- A complete graph with vertices has edges.
- For a complete graph , the number of Hamilton cycles is when cycles counted in reverse are considered the same.
- Every Hamilton cycle contains a Hamilton path, but a graph can have a Hamilton path without having a Hamilton cycle.
Vocabulary
- Graph
- A graph is a set of vertices connected by edges.
- Vertex Degree
- The degree of a vertex is the number of edges touching that vertex.
- Euler Path
- An Euler path is a route through a graph that uses every edge exactly once.
- Euler Circuit
- An Euler circuit is an Euler path that starts and ends at the same vertex.
- Hamilton Path
- A Hamilton path is a route through a graph that visits every vertex exactly once.
- Hamilton Cycle
- A Hamilton cycle is a Hamilton path that returns to its starting vertex.
Common Mistakes to Avoid
- Confusing Euler paths with Hamilton paths is wrong because Euler paths require using every edge once, while Hamilton paths require visiting every vertex once.
- Ignoring connectedness is wrong because Euler degree rules apply only when all non-isolated vertices belong to one connected component.
- Assuming two odd vertices means an Euler circuit exists is wrong because exactly odd vertices allow an Euler path, not a circuit.
- Repeating a vertex in a Hamilton path is wrong because each vertex may be visited exactly once, except the starting vertex repeats at the end of a Hamilton cycle.
- Using degree rules to prove a Hamilton path exists is wrong because the simple odd and even degree tests are for Euler paths and circuits, not Hamilton paths.
Practice Questions
- 1 A connected graph has vertex degrees . Does it have an Euler path, an Euler circuit, both, or neither?
- 2 A connected graph has vertex degrees . Does it have an Euler path? If so, where must the path start and end?
- 3 How many edges are in the complete graph ? Use .
- 4 A graph has a Hamilton cycle but no Euler circuit. Explain how this can happen by comparing the requirements for vertices and edges.
Understanding Euler & Hamilton Paths Reference
A useful first step is to draw the graph clearly and make a small degree table. The degree of a vertex is the number of edges that touch it. A loop contributes two to the degree because it enters and leaves the same vertex.
When you add all degrees, the total is always even. This is called the handshaking idea. Each edge has two ends, so it adds two to the total degree count.
As a result, odd-degree vertices always occur in pairs. This explains why a route that uses each edge once can have only certain start and end patterns.
It is not a memorized trick. It comes from the way a route enters and leaves vertices.
For an edge-tracing route, think about what happens at a middle vertex. Each time the route arrives there, it needs an unused edge to leave by. Those arrivals and departures form pairs.
A vertex can fail to pair only at the beginning or the end of an open route. Before applying any degree rule, check that all non-isolated parts of the graph belong to one connected piece. A graph may have suitable degrees yet still be impossible to trace in one route if a separate cluster of edges cannot be reached.
Isolated vertices need careful treatment in textbook questions. They do not affect an edge-tracing route, but they matter when a task requires visiting every vertex.
Vertex-visiting routes need a different kind of reasoning. The main issue is whether the graph has enough links to move through every location without getting trapped or forced to return too early. A vertex with only one edge is a warning sign.
In a Hamilton path, such a vertex must be at an endpoint. In a Hamilton cycle, every vertex needs two route connections, so a vertex of degree one makes a cycle impossible. A cut vertex is another important clue.
If removing one vertex splits the graph into several separate pieces, a Hamilton cycle cannot exist because the cycle would need to pass through that vertex too many times. These observations can rule out possibilities quickly, though they cannot prove every possible route exists.
In real settings, the distinction changes the goal of a problem. A street sweeper or a person inspecting cables may want to cover each road segment once, which resembles an Euler problem. A delivery driver visiting a list of stops once, or a machine visiting stations in a fixed sequence, resembles a Hamilton problem.
Real routes often add distance, traffic, time limits, or one-way streets, so the pure graph model is only the starting point. When solving by hand, label vertices, mark used edges or visited vertices, and record each move.
For cycles, verify the final return separately. Many errors happen when a route repeats an edge without noticing, skips a vertex, or treats a drawing crossing as a vertex when no dot is shown.