UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 10.1 Free with a free account
Hamiltonian Paths and Circuits
Discrete Mathematics · Chapter 10: Graph Theory: Hamiltonian Circuits, Coloring, and RepresentationsSection 10.1 · lesson 67 of 8713 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Discrete Mathematics.
Lesson complete
Earn the 4 college credits for Discrete Mathematics
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Weighted Graphs and the Traveling Salesman Problem →← Eulerizing a GraphNext lesson: Weighted Graphs and the Traveling Salesman Problem →
In this lesson
Visit every vertex exactly once - and why no easy test exists.
- Define Hamiltonian paths and circuits
- Contrast them with Euler paths and circuits
- Explain why the existence question is NP-complete
- Apply Dirac's and Ore's theorems
Transcript
Everything said in the video, section by section (1,916 words). Read along, or search it.
Graph Theory: Hamiltonian Circuits, Coloring, and Representations
Hamiltonian Paths and Circuits
Chapter ten opens with a question that looks almost identical to the Euler circuit question, and turns out to be vastly harder. A Hamiltonian path visits every vertex of a graph exactly once. This section defines Hamiltonian paths and circuits, shows why no simple test for them is known, and develops two theorems, Dirac's and Ore's, that can still guarantee a circuit exists.
The Opening Problem
Reassembling a Genome
When a machine sequences a sample of DNA, it doesn't read a chromosome end to end. It shatters many copies of the molecule into millions of short, overlapping fragments, called reads. Then a computer must rebuild the original sequence from the fragments alone. One classical way to frame that is as a graph. Each read is a vertex. And an edge joins two reads whenever the tail of one plausibly overlaps the head of the other. Rebuilding the genome then means finding one ordering that uses every read exactly once, consistent with the overlaps. That's a walk through every vertex of the graph, exactly one time. It's called a Hamiltonian path. And it gets expensive as the number of reads grows, for a structural reason, not because of any one program's code.
Definitions
2 Kinds of "Visit Everything"
Throughout, G is a simple graph, and n is its number of vertices. Recall that an Euler path uses every edge exactly once, and vertices may repeat. An Euler circuit also returns to its start. A Hamiltonian path is a path that includes every vertex exactly once. Since no vertex repeats, it uses exactly n minus one edges, and its two ends needn't be adjacent. A Hamiltonian circuit, also called a Hamiltonian cycle, visits every vertex exactly once, and then returns to the start. It uses exactly n edges. Here's the easiest way to hold the contrast. An Euler circuit asks whether a route can use every road exactly once. A Hamiltonian circuit asks whether a route can visit every intersection exactly once. Roads are edges, and intersections are vertices. And satisfying one question tells you nothing about the other.
Figure 1
2 Graphs, 2 Independent Properties
Two small graphs make that precise. On the left is the bowtie, G one. It's two triangles sharing the vertex C. A, B, D and E have degree two, and C has degree four. Every degree is even, so by Euler's theorem, G one has an Euler circuit. For instance, A, B, C, D, E, C, and back to A. But it has no Hamiltonian circuit. Deleting C separates A and B from D and E entirely, and we'll see in a moment why that rules a circuit out. On the right is G two, a five-cycle with one added chord, from one to three. Vertices one and three have degree three, which is odd. So G two has an Euler path from one to three, but no Euler circuit. Yet G two plainly has a Hamiltonian circuit. The outer cycle, one, two, three, four, five, and back to one, visits every vertex once. It never even needs the chord. So each property can hold without the other. They're logically independent.
Lemma
Cut Vertices Block Hamiltonian Circuits
Here's the reason G one fails. A cut vertex is a vertex whose removal, along with its edges, leaves the graph disconnected. The lemma says that if a connected graph has a cut vertex, it has no Hamiltonian circuit. The proof is by contradiction. Suppose a Hamiltonian circuit exists, and it passes through the cut vertex v, as it must, since it visits every vertex. Delete v from the circuit. What's left runs through every other vertex, in order, so it's a Hamiltonian path on the remaining graph. Every edge of that path avoids v, so every one of them survives when v is removed. A path connects all its vertices, so the graph without v is still connected. That contradicts v being a cut vertex. So no Hamiltonian circuit can exist. But notice what kind of claim this is. Having no cut vertex is necessary for a Hamiltonian circuit. It isn't sufficient. Plenty of graphs without cut vertices still have no circuit.
Table 1
Euler Versus Hamilton
Here's the comparison side by side. Euler covers every edge exactly once, and vertices may repeat. Hamilton covers every vertex exactly once, and nothing may repeat. Euler's existence question has a complete if-and-only-if answer: degree parity. You check it in one pass over the degrees. For Hamiltonian circuits, no such condition is known. There are only sufficient conditions, or direct search. Deciding existence is N P complete. The names come from Leonhard Euler, and the Königsberg bridges problem of seventeen thirty-six. And from Sir William Rowan Hamilton, whose Icosian Game of eighteen fifty-seven asked for a route through all twenty vertices of a dodecahedron.
10.1.2
HAM-CIRCUIT Is NP-Complete
In the century and a half since Hamilton's puzzle, no simple test has been found. And that isn't just for lack of a clever theorem. It reflects a proven fact about how hard the question is. The decision problem, does G contain a Hamiltonian circuit, is N P complete. Richard Karp showed that in nineteen seventy-two, in a paper that established twenty-one problems as N P complete. Informally, a problem is in N P if any proposed solution can be verified quickly, in polynomial time. That's easy here. Handed an ordering, you check that it visits all n vertices once, and that consecutive vertices are joined by edges. N P complete means it's among the hardest problems in N P. Every other N P problem can be translated into it. So a fast algorithm for Hamiltonian circuits would give one for every problem in N P, and settle the P versus N P question. No such algorithm is known, and most complexity theorists suspect none exists, though that's unproven. Brute force is hopeless. A graph on n vertices has n minus one factorial, over two, possible circuits. For Hamilton's twenty vertices, that's about six point zero eight times ten to the sixteenth.
Backtracking
Build a Path, Abandon Dead Ends
A smarter approach is backtracking. Build a path one vertex at a time, and abandon any partial path as soon as it can't be completed. The function starts a path at the chosen vertex. Once the path holds all n vertices, it checks whether the last one is adjacent to the start, closing the circuit. Otherwise it tries each unvisited neighbor of the last vertex, adds it, and recurses. If that branch fails, it backtracks. It removes the neighbor, and tries the next one. In the worst case, this is still order n factorial. But on typical graphs, it prunes enormous parts of the search.
Worked Example
Tracing the Search on G3
Here's the search on a six-vertex graph, G three. It has nine edges, and every vertex has degree exactly three. Starting from one, with each neighbor list in increasing order, the search builds one, two, three, six, four, and then five. That uses all six vertices. But five isn't adjacent to one, so the path can't close. The search backtracks from five, then from the dead end at four, back to six. There, it tries six's next neighbor, five. The path one, two, three, six, five, four uses every vertex, and four is adjacent to one. So the circuit closes, one, two, three, six, five, four, and back to one. Even on a graph this small, the search needed a backtrack. Naive enumeration would have faced sixty candidate circuits, with no pruning at all.
10.1.3
Sufficient Conditions: Dirac and Ore
Since there's no efficient if-and-only-if test, graph theorists developed sufficient conditions. These are properties that, when present, guarantee a Hamiltonian circuit exists, without exhibiting one. Dirac's theorem, from nineteen fifty-two. Let G be a simple graph with at least three vertices. If every vertex has degree at least n over two, then G has a Hamiltonian circuit. Ore's theorem, from nineteen sixty. Same setting. If, for every pair of non-adjacent vertices, their degrees add up to at least n, then G has a Hamiltonian circuit. Here's how the two relate. If every degree is at least n over two, then any two degrees sum to at least n. So every graph that satisfies Dirac also satisfies Ore. Ore's theorem generalizes Dirac's.
Worked Examples
Dirac on G3, Ore Where Dirac Fails
Go back to G three. It has six vertices, so n over two is three, and every vertex has degree three. Dirac's hypothesis holds. So Dirac's theorem guarantees a Hamiltonian circuit, which matches the one the search found. The theorem lets you conclude a circuit exists without searching at all. Now take G four, on five vertices, with eight edges. Vertex one has degree two, the others have degrees four, four, three and three. Dirac's threshold is two and a half, and vertex one falls short. So Dirac's theorem says nothing, either way. Ore's theorem asks only about non-adjacent pairs. Of the ten pairs of vertices, just two are non-adjacent, one and four, and one and five. Each sums to two plus three, which is five, meeting the threshold of five. So Ore guarantees a circuit. One is one, two, four, five, three, and back to one. The theorem certifies that a circuit exists. It doesn't tell you which.
Sufficient, Not Necessary
When the Theorems Are Silent
Both theorems are sufficient, not necessary. A plain six-cycle shows it. Every vertex has degree two, short of Dirac's threshold of three. Any two non-adjacent vertices sum to four, short of Ore's threshold of six. Both hypotheses fail. Yet the six-cycle is, by construction, its own Hamiltonian circuit. So there are three tools. Dirac needs one pass over the degrees, and suits dense, nearly regular graphs. Ore checks every non-adjacent pair, and helps when low-degree vertices sit away from high-degree ones. Direct search is order n factorial in the worst case. Use it when both hypotheses fail, or when you need the actual circuit, not just a guarantee.
10.1.4
Back to the Genome
Back to the genome. Suppose four short reads come from a small circular genome: A T G C, T G C A, G C A T, and C A T G. Let read X precede read Y when X's last three letters match Y's first three. Then each read leads to the next, and the last leads back to the first. The overlap graph is a directed four-cycle, a Hamiltonian circuit, rebuilding the repeating circle A T G C. That's fitting, since many bacterial chromosomes and plasmids really are circular. Real runs produce millions of reads, with errors and repeats. At that scale, the Hamiltonian search is exactly the exponential problem we just met. So short-read assemblers commonly switch to a different construction, the de Bruijn graph, where fixed-length substrings become edges instead of vertices. Assembly then becomes an Euler path problem, solvable by a degree test instead of a search. Pevzner, Tang and Waterman described that approach in two thousand one. The vertex-versus-edge distinction is the whole reason it works.
Takeaways
Every Vertex, Exactly Once
To summarize. Hamiltonian paths and circuits visit every vertex exactly once. Euler paths and circuits use every edge exactly once. And the two properties are logically independent. Deciding whether a Hamiltonian circuit exists is N P complete, as Karp showed in nineteen seventy-two. A cut vertex rules out a Hamiltonian circuit. But having no cut vertex guarantees nothing. Dirac's and Ore's theorems are sufficient conditions that guarantee a circuit. Ore's generalizes Dirac's. And a graph that fails both, like a plain cycle, can still have one. Here's something to think about. A graph has ten vertices, and every vertex has degree four, below Dirac's threshold of five. A student concludes that G has no Hamiltonian circuit. What exactly is wrong with that reasoning? And what might a graph look like that fails Dirac's hypothesis at every vertex, but still has a Hamiltonian circuit?
About Discrete Mathematics at UPI Study
Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take Discrete Mathematics with UPI Study
Where the credit goes
Universities that work with NCCRS
Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Hamiltonian Paths and Circuits
What is the difference between a Hamiltonian circuit and an Euler circuit?
Why is deciding whether a graph has a Hamiltonian circuit NP-complete?
How do you use Dirac's theorem and Ore's theorem to show a graph has a Hamiltonian circuit?
If a graph fails Dirac's and Ore's conditions, does it have no Hamiltonian circuit?
About the Discrete Mathematics course
How many college credits is Discrete Mathematics?
How much does Discrete Mathematics cost and what is included?
Which universities accept UPI Study credits?
How long does Discrete Mathematics take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 4 credits in Discrete Mathematics.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
4 credits · NCCRSEnroll →