1. Two questions that look the same
Given a graph, two natural traversal questions present themselves:
- Edges: can I walk through the graph using every edge exactly once?
- Vertices: can I walk through the graph visiting every vertex exactly once?
The first is the Eulerian question. The second is the Hamiltonian question. They sound interchangeable. They are not. Euler — in 1736, dealing with the bridges of Königsberg — gave a complete characterization in terms of vertex degrees that you can check in linear time. Hamilton's version, despite three centuries of attention, has no analogous characterization: deciding whether a Hamiltonian cycle exists is NP-complete. The gap between these two problems is one of the cleanest examples in mathematics of how superficial similarity can hide a chasm of difficulty.
Eulerian = Edges; Hamiltonian = Houses (vertices). Mixing them up is the single most common error in this material.
2. Eulerian circuits and trails
A trail is a walk with no repeated edges. An Eulerian trail is a trail that uses every edge of the graph. If it starts and ends at the same vertex, it's an Eulerian circuit.
Euler's insight is that you only need to look at one local quantity — the degree of each vertex — to decide whether such a trail exists.
Let $G$ be a connected graph (with at least one edge). Then:
- $G$ has an Eulerian circuit iff every vertex has even degree.
- $G$ has an Eulerian trail (but no circuit) iff exactly two vertices have odd degree. The trail must start at one of them and end at the other.
- If there are any other count of odd-degree vertices, no Eulerian trail exists.
The reasoning is almost embarrassingly direct. Each time a trail enters a vertex, it must also leave — except possibly at the start and end. So every "interior" vertex contributes a paired entry-and-exit per visit, meaning its degree must be even. The start and end vertices, if different, each contribute one unpaired half — making their degrees odd. If start equals end (a circuit), there are no unpaired halves, and every degree is even.
That's the necessity. Sufficiency takes a tiny construction: start anywhere, walk until you get stuck (which will always be back at the start, by the parity argument); if any edges remain, splice in a sub-circuit from an already-visited vertex. This is Hierholzer's algorithm, and it runs in $O(|E|)$ time.
For directed graphs, "even degree" is replaced by "in-degree equals out-degree at every vertex." Plus strong connectivity. Same flavor, slightly different bookkeeping.
3. Why Königsberg fails
Königsberg (now Kaliningrad) sat across the Pregel river in two banks plus two islands, connected by seven bridges. The townspeople's puzzle: can you walk through the city crossing every bridge exactly once? Euler's reformulation collapses the geography into a graph — one vertex per landmass, one edge per bridge.
Read off the degrees: $A$ has degree 5, and $N$, $S$, $B$ each have degree 3. Four odd-degree vertices. Euler's theorem allows 0 (for a circuit) or 2 (for a trail). With four, no Eulerian trail of any kind can exist. The townspeople weren't bad at puzzles — they were trying to do something logically impossible, and Euler proved it.
Euler's 1736 paper on Königsberg is generally treated as the founding document of graph theory. He extracted the abstract structure (vertices and edges) from a concrete geographic problem, then proved a theorem about that structure — exactly the move that makes a mathematical discipline.
4. Hamiltonian circuits and paths
A Hamiltonian path visits every vertex of $G$ exactly once. A Hamiltonian cycle (or circuit) is a Hamiltonian path that returns to its starting vertex. A graph that contains a Hamiltonian cycle is called Hamiltonian.
The phrasing change is one word — edges to vertices — and the consequences are enormous. There is no known characterization of Hamiltonian graphs in terms of any local invariant. The decision problem "Does this graph have a Hamiltonian cycle?" is NP-complete (Karp, 1972). The same is true for Hamiltonian path. In plain terms: if you had a polynomial-time algorithm for Hamiltonicity, you'd have one for every problem in NP, and you would collect a million dollars.
The intuition for why is in the contrast with Euler. Eulerian-ness is detected by a local condition (degree parity), and a local condition can be checked by inspecting each vertex independently. Hamiltonian-ness is intrinsically global: a single missing edge in the right place can destroy the only Hamiltonian cycle in a graph, while leaving every local statistic almost unchanged.
Don't expect a "degree-style" criterion for Hamilton. Every Hamiltonian theorem that does exist is either a sufficient condition (some graphs satisfy it, some Hamiltonian graphs don't), or so abstract that checking it is itself hard.
5. Dirac and Ore — sufficient conditions
If there's no clean iff, the next best thing is a clean if. Two simple degree-based conditions guarantee Hamiltonicity in any graph that satisfies them; both are easy to state and easy to check.
If $G$ is a simple graph on $n \geq 3$ vertices and every vertex has degree at least $n/2$, then $G$ is Hamiltonian.
If $G$ is a simple graph on $n \geq 3$ vertices and $\deg(u) + \deg(v) \geq n$ for every pair of non-adjacent vertices $u, v$, then $G$ is Hamiltonian.
Ore is strictly stronger than Dirac: any graph where every vertex has degree $\geq n/2$ obviously has every pair (adjacent or not) summing to at least $n$, but the converse fails. Both are sufficient, not necessary — long cycles $C_n$ with $n$ large are Hamiltonian but have minimum degree 2, far below $n/2$.
| Question | Eulerian | Hamiltonian |
|---|---|---|
| What gets used exactly once? | Every edge | Every vertex |
| Characterization | Even-degree condition (iff) | None known |
| Decision complexity | $O(|V| + |E|)$ | NP-complete |
| Construction | Hierholzer, $O(|E|)$ | Backtracking, exponential worst-case |
| Sufficient conditions | (already iff) | Dirac, Ore, Chvátal–Erdős, ... |
6. Graph coloring and $\chi(G)$
Pivoting to the third question. Forget traversal — instead, ask whether you can label the vertices of a graph with colors so that no edge has both endpoints the same color.
A proper $k$-coloring of $G$ is a function $c : V(G) \to \{1, 2, \ldots, k\}$ such that $c(u) \neq c(v)$ whenever $uv$ is an edge. The chromatic number $\chi(G)$ is the smallest $k$ for which such a coloring exists.
So $\chi(G)$ is a single integer that summarizes how "conflict-rich" the graph is. A graph with no edges has $\chi = 1$ (everything is the same color). A complete graph $K_n$ has $\chi = n$ (every vertex is adjacent to every other, so they all need distinct colors). Most interesting graphs sit between.
Two easy bounds anchor the picture. From below: $\chi(G) \geq \omega(G)$, the size of the largest clique — a $k$-clique forces $k$ different colors. From above: a simple greedy argument gives $\chi(G) \leq \Delta(G) + 1$, where $\Delta(G)$ is the maximum degree. (Order the vertices arbitrarily; color each one with the smallest color not yet used on its neighbors. At most $\Delta$ colors are forbidden, so $\Delta + 1$ always suffice.)
7. Bipartite, odd cycles, and $\chi = 2$
The cleanest non-trivial case of coloring is $\chi = 2$. A graph is bipartite if its vertices split into two sets $A$ and $B$ such that every edge crosses from $A$ to $B$. Color $A$ red, $B$ blue, and you have a proper 2-coloring. So bipartite ⇒ $\chi \leq 2$.
The converse holds too — a graph with a proper 2-coloring is bipartite, because the two color classes give exactly the bipartition. But here's the deeper fact: bipartite graphs are exactly the graphs with no odd cycle.
A graph is bipartite ⇔ it has chromatic number at most 2 ⇔ it contains no odd cycle.
Why no odd cycle? Imagine alternating red and blue as you walk around a cycle. The colors switch on every step. If you return to where you started after an odd number of steps, you've ended on the opposite color from where you began — contradiction. Even-length cycles cause no problem; odd-length ones are exactly what breaks 2-colorability.
This is the prototype for a recurring pattern in coloring theory: a structural feature (odd cycles, triangles, planarity) controls a numerical invariant ($\chi$). Find the right structural cause and you can read off the bound.
8. Four Color, Brooks, Vizing
The Four Color Theorem
The most famous result in graph coloring — and one of the most famous in all of mathematics — is the Four Color Theorem: every planar graph is 4-colorable. Equivalently, every map drawn in the plane can be colored using at most four colors so that no two adjacent regions share a color.
The conjecture is due to Francis Guthrie in 1852, posed while coloring a map of the counties of England. Alfred Kempe published a proof in 1879 that stood for eleven years before Percy Heawood found a fatal flaw in 1890. Heawood salvaged the argument to give the Five Color Theorem, which is genuinely elegant and provable on a chalkboard. The four-color version resisted every attack until 1976, when Kenneth Appel and Wolfgang Haken finally proved it — with the assistance of about 1200 hours of computer time spent verifying thousands of unavoidable configurations.
That computer-assisted character was controversial at the time. Mathematicians were used to proofs they could read. Subsequent work (notably Gonthier's 2005 formal verification in Coq) has since put the result on firmer footing, but the four-color theorem remains a landmark — both for its mathematical content and for being the first major theorem whose proof required a computer.
The four-color bound is specific to planar graphs — graphs that can be drawn in the plane with no edge crossings. The complete graph $K_5$ is not planar and needs five colors, no contradiction. The Petersen graph is also non-planar and has $\chi = 3$ (the planarity hypothesis is sufficient, not necessary).
Brooks's theorem
The greedy upper bound $\chi(G) \leq \Delta(G) + 1$ is rarely tight. Brooks's theorem (1941) tells you exactly when it is.
For any connected simple graph $G$, $\chi(G) \leq \Delta(G)$ — unless $G$ is a complete graph $K_n$ or an odd cycle, in which case $\chi(G) = \Delta(G) + 1$.
So the greedy bound is off by one only in those two families of "tight" cases. For complete graphs, $\chi = n$ and $\Delta = n - 1$, off by one. For an odd cycle, $\chi = 3$ and $\Delta = 2$, off by one. Every other connected graph achieves $\chi \leq \Delta$ — typically with room to spare.
Vizing's theorem for edges
Coloring isn't restricted to vertices. You can also ask for a proper edge coloring: assign colors to edges so that no two edges sharing an endpoint get the same color. The minimum number of colors required is the chromatic index $\chi'(G)$.
For edges, the gap between necessity and sufficiency is wonderfully tight:
For any simple graph $G$, the chromatic index satisfies $\chi'(G) \in \{\Delta(G),\ \Delta(G) + 1\}$.
Two possibilities, no more. Graphs achieving $\chi' = \Delta$ are called Class 1; those needing $\Delta + 1$ are Class 2. Deciding which class a given graph is in is itself NP-complete in general — a recurring theme in coloring theory, where existence is constrained beautifully but identification is hard.
9. Where this shows up
Coloring isn't just a pretty puzzle. The chromatic number is the abstract solution to a surprisingly wide range of practical scheduling problems.
Timetabling
Build a graph with one vertex per class, and an edge between two classes whenever they share a student (or a teacher, or a room). A proper coloring assigns each class to a time slot such that no two slots conflict. The chromatic number is the minimum number of time slots needed. This is the canonical example in textbooks for a reason — it captures real institutional pain.
Register allocation in compilers
A compiler has to map an unbounded supply of program variables onto a small fixed number of CPU registers. Build the interference graph: one vertex per variable, an edge between two variables if they're "alive" at the same time (and so can't share a register). A proper coloring with $k$ colors is a register allocation using $k$ registers. Chaitin's classic algorithm makes this connection explicit, and modern compilers still use coloring-based allocators.
Frequency assignment
Radio towers, mobile cell sites, satellite uplinks — anywhere two transmitters that are close enough to interfere can't share a frequency. Vertices are transmitters, edges connect pairs that interfere, and the chromatic number is the minimum number of distinct frequencies you can get away with. Real instances add weights, lists, and distance-dependent constraints, leading to list coloring and other variants.
In every one of these problems, the underlying question is the same: "How few resources do I need to satisfy a pairwise non-conflict constraint?" Whenever you see that question, look for a hidden graph and ask for its chromatic number.
10. Common pitfalls
Eulerian is about edges; Hamiltonian is about vertices. Once you swap them in your head it's hard to unswap. Re-read the words "edge" and "vertex" in each definition until they stick.
The even-degree condition is for connected graphs. An isolated vertex has degree 0 (even) but obviously can't be part of any Eulerian circuit on the rest of the graph. Always check connectedness first.
A graph can be Hamiltonian without satisfying Dirac or Ore — long cycles are the easiest example. So failing the conditions tells you nothing. They give you a way to prove Hamiltonicity, not to rule it out.
A bipartite graph with at least one edge needs two colors, not one. Some students read "2-colorable" as "at most 2 colors needed when you bother" and conclude that one suffices. It doesn't, as long as there's an edge.
The Four Color Theorem says planar graphs are 4-colorable. Non-planar graphs can need arbitrarily many colors: $K_n$ needs $n$. Don't apply 4CT to a graph you haven't checked is planar.
The $\Delta + 1$ greedy bound holds, but the greedy algorithm can use many more colors than $\chi$ depending on vertex order. There exist graphs where greedy with the wrong order uses unboundedly more colors than the optimum.
11. Worked examples
Example 1 · Does $K_4$ have an Eulerian circuit?
The complete graph $K_4$ has 4 vertices, each adjacent to all 3 others, so every vertex has degree 3 — odd. With four odd-degree vertices, Euler's theorem says there's no Eulerian trail of any kind. (Compare $K_5$, where every vertex has degree 4 — all even, so $K_5$ does have an Eulerian circuit.) General pattern: $K_n$ has an Eulerian circuit iff $n$ is odd.
Example 2 · Apply Dirac to $K_{3,3}$
The complete bipartite graph $K_{3,3}$ has $n = 6$ vertices, each of degree 3. Dirac's condition requires every degree to be at least $n/2 = 3$. The minimum degree is exactly 3 — Dirac is satisfied (just barely), so $K_{3,3}$ is Hamiltonian. An explicit Hamiltonian cycle: $a_1, b_1, a_2, b_2, a_3, b_3, a_1$.
Example 3 · What is $\chi(C_5)$?
$C_5$ is the 5-cycle — an odd cycle. By the bipartite characterization, it isn't 2-colorable (it contains itself as an odd cycle). And 3 colors suffice: color the vertices $1, 2, 1, 2, 3$ as you go around. So $\chi(C_5) = 3$. This matches Brooks's theorem: $C_5$ is one of the exceptions where $\chi = \Delta + 1$ (here $\Delta = 2$).
Example 4 · Petersen graph: $\chi$ and Hamiltonicity
The Petersen graph has 10 vertices, each of degree 3. It contains odd cycles (e.g., the outer 5-cycle), so it's not bipartite — $\chi \geq 3$. And 3 colors do suffice via an explicit assignment, so $\chi(\text{Petersen}) = 3$. By Brooks, the bound $\chi \leq \Delta = 3$ holds since the Petersen graph is neither complete nor an odd cycle.
On Hamiltonicity, the Petersen graph is famously not Hamiltonian — though it has a Hamiltonian path. It's the smallest 3-regular graph with this property, and a favorite counterexample throughout graph theory.
Example 5 · Classroom timetabling as coloring
Suppose six classes A, B, C, D, E, F share students such that the conflict pairs are AB, AC, BC, CD, DE, EF, AF. Build a graph with these edges. Vertex A has degree 3 (B, C, F); the rest have degree 2 or 3. Greedy upper bound is $\Delta + 1 = 4$. But A–B–C forms a triangle, so $\chi \geq 3$. A valid 3-coloring: A=1, B=2, C=3, D=1, E=2, F=3 (check each edge — every endpoint pair differs). Three time slots suffice.