maths.free › Discrete Math & Logic › Euler and Hamilton paths
Euler and Hamilton paths
Walks using every edge once, Euler's degree condition, walks visiting every vertex once, and why the second is so much harder.
An Euler trail uses every edge of a graph exactly once, and an Euler circuit is one that ends where it started. Euler's question was whether the seven bridges of Königsberg could be crossed in this way, and his answer is a complete characterisation. A connected graph has an Euler circuit if and only if every vertex has even degree. It has an Euler trail that is not a circuit if and only if exactly two vertices have odd degree, and then the trail must start at one of them and end at the other.
The necessity is a counting argument: each time a trail passes through a vertex it uses two edges there, one in and one out, so every vertex other than the ends has even degree. The sufficiency is constructive. Start anywhere and walk along unused edges; with all degrees even you can only get stuck back at the start, having made a closed trail. If edges remain, some unused edge touches a vertex on the trail (the graph is connected), so walk a second closed trail from there and splice it in. Repeating this is Hierholzer's algorithm, and it runs in time proportional to the number of edges.
A Hamilton path visits every vertex exactly once, and a Hamilton cycle returns to the start. The definitions look symmetrical to Euler's, but no simple condition on degrees decides them. There are useful sufficient conditions: Dirac's theorem says a simple graph on \( n \ge 3 \) vertices in which every vertex has degree at least \( n/2 \) has a Hamilton cycle. And there are useful obstacles: removing \( k \) vertices from a graph with a Hamilton cycle leaves at most \( k \) components, and a bipartite graph with parts of different sizes has no Hamilton cycle.
In the complete graph \( K_n \), a Hamilton cycle is an ordering of the vertices up to rotation and direction. Fix the starting vertex, order the other \( n - 1 \) in \( (n-1)! \) ways, and divide by 2 for the direction: \( (n-1)!/2 \) cycles. The example finds 360 for \( K_7 \). The travelling salesperson problem asks for the cheapest of them, and trying them all is hopeless beyond a few dozen cities.
Picture it: an Euler circuit is drawing the figure without lifting the pen and without retracing a line; a Hamilton cycle is a tour that calls at every town once. The first is about lines, the second about dots, and the difference in difficulty is enormous.
Think it: for an Euler question, count odd-degree vertices and check connectivity: that settles it. For a Hamilton question, look for a proof of existence (Dirac, or an explicit cycle) or a proof of impossibility (a set of vertices whose removal leaves too many components, or a parity argument on a bipartite graph). Deciding the question for a general graph is NP-complete, which is taken up in the lesson on reductions.
Worked example · 6!/2
Step by step
- \frac{720}{2} = 360
Evaluate.
Reveal the answer
Now you Pick a problem, or type or draw your own. Every step, a picture, the answer hidden until you ask.
Symbols used here
Tap any symbol for the full definition, a picture, and what every letter in it means.
How to: Euler and Hamilton paths
- For Euler questions, check that the edges lie in one connected component.
- Count the vertices of odd degree: 0 gives a circuit, 2 gives a trail between them, anything else gives neither.
- To construct the circuit, follow unused edges and splice in closed sub-trails (Hierholzer).
- For Hamilton questions, try Dirac's condition or build a cycle; to rule one out, remove vertices and count components.
Questions people ask
Why can there not be exactly one vertex of odd degree?
By the handshake lemma the number of odd-degree vertices is even, so it is 0, 2, 4, and so on, never 1.
Does a graph with an Euler circuit always have a Hamilton cycle?
No. Two triangles sharing one vertex have all degrees even, so an Euler circuit exists, but any closed tour through all five vertices must pass through the shared vertex twice.
What makes mathematics "discrete"?
It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.
How does a proof by induction work?
Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.
What order should I take these lessons in?
Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.
Is discrete mathematics the same as the maths of computer science?
Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.
Do I need calculus for this course?
No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.
More in Discrete Math & Logic
Truth tablesSums and inductionProof by inductionAlgorithms and growth of functionsPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsThe pigeonhole principleSolving linear recurrence relationsGraphs: degrees, paths and connectivityTrees and spanning trees