Euler & Hamilton Paths Reference Cheat Sheet

A printable reference covering Euler paths, Euler circuits, Hamilton paths, Hamilton cycles, vertex degree tests, and complete graph edge counts for grades 10-12.

TopicsGraphs Algorithms Counting Mathematics Study Guide

Download PNG

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Math Vocabulary

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 $0$ or $2$ 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 $2$ 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 $n$ vertices has $\frac{n(n-1)}{2}$ edges.
For a complete graph $K_n$ , the number of Hamilton cycles is $\frac{(n-1)!}{2}$ 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 $2$ 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 $2, 4, 4, 6, 8$ . Does it have an Euler path, an Euler circuit, both, or neither?
2 A connected graph has vertex degrees $1, 2, 2, 3, 4, 4$ . Does it have an Euler path? If so, where must the path start and end?
3 How many edges are in the complete graph $K_8$ ? Use $\frac{n(n-1)}{2}$ .
4 A graph has a Hamilton cycle but no Euler circuit. Explain how this can happen by comparing the requirements for vertices and edges.

Sign in to save