← SciSim / Mathematics

Graph Theory: Eulerian, Hamiltonian, Coloring

Discrete structures of vertices and edges — three classical problems with sharp algorithmic boundaries.
🎓 Tier: Standard Undergraduate (Discrete Math)

📊 Section 1 — Interactive Simulation

Pick a graph preset (or build your own by adding/removing edges and dragging nodes). Switch modes to find Eulerian circuits, Hamiltonian paths, or proper colorings — each with its own algorithm and animation.

graph view
|V| (vertices)
—
|E| (edges)
—
connected?
—
odd-degree count
—
Eulerian circuit?
—
Hamiltonian path?
—
χ(G) (chromatic#)
—
step / total
0 / 0

Animation

Graph Preset

Edit Graph

Tap two nodes to toggle edge. Drag nodes to reposition.

Algorithm Parameters

Display Options

Tips

• Königsberg has 4 odd vertices → no Eulerian circuit (Euler's 1736 result).
• K₅ is non-planar; minimum colors needed is 5.
• Petersen graph is famously NOT Hamiltonian — try to find a path!
• Hamiltonian search is NP-complete; expect slow on n>14.

💡 Section 2 — The Idea, Step by Step

From "dots and lines" to three deep algorithmic questions — built up one layer at a time.

Start with something you already know. Draw a few dots on paper and connect some of them with lines: that picture is a graph. The dots are vertices, the lines are edges. Friends linked by friendships, cities linked by roads, web pages linked by hyperlinks — all the same object. Two playful puzzles live inside every such picture. Can you trace every line without lifting your pen and without going over any line twice? And, separately, can you tour every dot exactly once? They sound almost the same, yet they hide a surprising gap in difficulty.

Now name things. The number of lines meeting a vertex is its degree, $\deg(v)$. Here is the one rule that cracks the first puzzle: if you add up the degrees of all the vertices, you count each edge twice — once at each end — so $\sum_v \deg(v) = 2\abs{E}$. This is the handshake lemma. Euler saw that to trace every edge and get back home, you must enter and leave each vertex equally often, which forces every degree to be even. Königsberg's four landmasses had degrees $3,3,3,5$ — all odd — so the famous "cross all seven bridges once and return" walk is simply impossible. That single observation, in 1736, launched graph theory.

The ideas to remember

A connected graph has an Eulerian circuit $\iff$ every vertex has even degree. And greedy coloring never needs more than $\chi(G) \le \Delta(G)+1$ colors.

The precise versions sharpen all this. Eulerian circuits are local: just check whether every degree is even, then Hierholzer's algorithm builds the circuit in $O(\abs{E})$ time. The Hamiltonian question — visit every vertex once — has no such shortcut; it is NP-complete, which is why the sim runs an exponential backtracking search. Coloring asks for the fewest colors $\chi(G)$ so that no edge joins two same-colored vertices, and the greedy pass guarantees $\chi(G)\le\Delta(G)+1$. In the simulation above, the mode tabs switch between these three problems, the preset dropdown loads classic graphs, and the $n$ and $p$ sliders generate random Erdős–Rényi graphs.

Try this in the sim above: load Königsberg and watch the "odd-degree count" read 4 — Euler mode reports no circuit. Switch the preset to Cycle C₆: now every degree is 2, and an Eulerian circuit appears at once. Finally choose the Petersen graph, run Hamiltonian mode, and watch the search backtrack and fail — it is the smallest 3-regular graph with no Hamiltonian cycle.

📐 Section 3 — Three Theorems

Each problem has a sharp characterization or bound — though their algorithmic difficulty varies wildly.

Euler's Theorem (1736)

A connected multigraph $G$ has an Eulerian circuit (closed walk using every edge exactly once) if and only if every vertex has even degree.

Variant: $G$ has an Eulerian trail (open) iff exactly two vertices have odd degree (those become the endpoints).

Dirac's & Ore's Sufficient Conditions for Hamiltonicity

Dirac (1952): If $G$ is a simple graph with $n \geq 3$ vertices and every vertex has $\deg(v) \geq n/2$, then $G$ has a Hamiltonian cycle (cycle through every vertex).
Ore (1960): If for every pair of non-adjacent $u, v$, $\deg(u) + \deg(v) \geq n$, then $G$ has a Hamiltonian cycle.

No "if and only if" exists: deciding Hamiltonicity is NP-complete (Karp, 1972).

Four Color Theorem & Brooks' Theorem

Four Color (Appel–Haken, 1976): Every planar graph is 4-colorable; $\chi(G_{\text{planar}}) \leq 4$.
Brooks (1941): For any connected graph $G$ that is not a complete graph and not an odd cycle, $\chi(G) \leq \Delta(G)$, the maximum degree.

Symbol Table

SymbolMeaningType
$G = (V, E)$ Graph: vertex set $V$ and edge set $E$ Pair of finite sets
$n = \abs{V}$ Number of vertices (order of $G$) Positive integer
$m = \abs{E}$ Number of edges (size of $G$) Non-negative integer, $\leq \binom{n}{2}$
$\deg(v)$ Degree: number of edges incident to $v$ Integer in $[0, n-1]$ (simple graph)
$\Delta(G)$ Maximum degree over all vertices Integer
$\chi(G)$ Chromatic number — minimum colors for proper coloringPositive integer
$K_n$ Complete graph: every pair of vertices adjacent $\binom{n}{2}$ edges
$C_n$ Cycle on $n$ vertices $n$ edges, all degrees 2
$K_{p,q}$ Complete bipartite: $p+q$ vertices in two parts $pq$ edges

Proof — Euler's Theorem (Sufficient Direction)

Step 1 · Necessity (easy direction)
Suppose $G$ has an Eulerian circuit $C$. Each time $C$ enters a vertex $v$ along an edge, it must leave along a different edge (since each edge is used once). So edges at $v$ pair up: $\deg(v)$ is even.
Step 2 · Sufficiency: setup
Suppose $G$ is connected and every vertex has even degree. We construct an Eulerian circuit by induction on $\abs{E}$. Base: if $\abs{E}=0$, the trivial empty circuit works.
Step 3 · Find any cycle
Start at any vertex $v_0$ and walk, never repeating edges. Since every vertex has even degree, whenever we enter a vertex, there is an unused edge to leave by — except possibly back at $v_0$. So eventually we return to $v_0$, giving a closed trail $C_0$.
Step 4 · Hierholzer's splice argument
Remove edges of $C_0$ from $G$, leaving $G'$. In $G'$, every vertex still has even degree (we removed edges in pairs at each vertex along the cycle). Each connected component of $G'$ touches some vertex of $C_0$ (since original $G$ was connected). By induction, each component has an Eulerian circuit — splice them into $C_0$ at the touching vertices.
Step 5 · Hierholzer's algorithm — explicit
Practically: maintain a stack. Start at any vertex; while current vertex has unused edges, push it and traverse an edge to the next vertex. When stuck, pop and append to circuit. This runs in $O(\abs{E})$ time and produces an Eulerian circuit.
Step 6 · Why Hamiltonian is fundamentally harder
Eulerian condition is local: it depends only on degrees. Hamiltonian condition has no such characterization — deciding "is there a cycle through every vertex?" is NP-complete (Karp 1972). The simulation runs an exponential-time backtracking DFS; on dense graphs with $n=15$ this can take a while.
Step 7 · Coloring — the greedy bound
Process vertices in some order $v_1, \ldots, v_n$. Assign each $v_i$ the smallest color not used among its already-colored neighbors. Since at most $\deg(v_i)$ colors are forbidden, $\Delta(G)+1$ colors always suffice: $\chi(G) \leq \Delta(G)+1$. Brooks' theorem strengthens to $\chi(G) \leq \Delta(G)$ except for $K_n$ and odd cycles. Order matters: Welsh–Powell orders vertices by decreasing degree and is often near-optimal in practice. $\boxed{\chi(G) \leq \Delta(G)+1.}$

Simulation ↔ Symbol Mapping

nodes on canvas vertex set $V$
edges between nodes edge set $E$
readout |V|, |E| $n, m$ — order and size
readout odd-degree countnumber of vertices with odd $\deg$ — Euler circuit exists ⇔ this is 0
readout χ(G) chromatic number, computed as result of greedy coloring (upper bound; exact for small $n$)
mode Euler runs Hierholzer's algorithm; trail of edges in animation = current circuit being built
mode Hamilton DFS backtracking: visit unvisited neighbors; current path highlighted; failed branches fade
mode Color greedy coloring with Welsh–Powell ordering; colors assigned in animation order

Worked Example — Königsberg Bridges

Königsberg's two islands and the riverbanks gave 4 land masses connected by 7 bridges. As a multigraph: $V = \{N, S, E, W\}$ (north bank, south bank, east island, west island), with degrees $\deg(N)=3$, $\deg(S)=3$, $\deg(E)=3$, $\deg(W)=5$.

Sum check: $3+3+3+5 = 14 = 2\abs{E}$ ✓ ($14/2 = 7$ bridges, the famous count).

All four vertices have odd degree. By Euler's theorem, no Eulerian circuit exists — and not even an Eulerian trail (which needs exactly 0 or 2 odd vertices).

Conclusion (Euler 1736): No walk can cross every bridge exactly once and return. The negative answer launched graph theory as a mathematical discipline. $\boxed{\text{Königsberg is not Eulerian.}}$

Reference: Rosen, K. — Discrete Mathematics and Its Applications, 8th ed., Ch. 10 §10.1–10.5; Diestel, R. — Graph Theory, 5th ed., Ch. 1 (basics) & Ch. 5 (coloring); Bondy & Murty — Graph Theory, Springer GTM 244 (2008); West, D. — Introduction to Graph Theory, 2nd ed., Ch. 1.2 (Euler), Ch. 7 (Hamiltonicity), Ch. 5 (coloring).

❓ Section 4 — Frequently Asked Questions

🧮Conceptual Why is Eulerian "easy" (polynomial) but Hamiltonian "hard" (NP-complete)?▶

Eulerian existence has a local characterization: just check parities of degrees. Once existence is confirmed, Hierholzer's algorithm constructs a circuit in linear time. Hamiltonian, however, has no such local test — there's no efficient property of vertices and edges that says "yes, a Hamiltonian path exists". You essentially have to search through possible orderings of vertices, and the best known algorithms are exponential (best general bound is $O^*(2^n)$ via Bellman–Held–Karp dynamic programming). NP-complete means: if you could decide Hamiltonicity in polynomial time, you could solve every problem in NP — including SAT, 3-coloring, factoring, and thousands more. So unless P = NP, Hamiltonian is genuinely hard.

Key takeaway: local properties (Eulerian) are easy; global properties (Hamiltonian) are NP-complete because no shortcuts to brute search are known.
🔬Simulation What is Hierholzer's algorithm doing in the Euler mode?▶

It maintains a stack and a circuit. Start at any vertex; mark it the "current". While the current vertex has unused edges, push it onto the stack and traverse one of its edges, deleting that edge as we go. When the current vertex has no more unused edges, pop it and append to the output circuit. Repeat until the stack is empty. Each edge is touched exactly twice (push and pop), so the total work is $O(\abs{E})$ — linear in the number of edges. The simulation animates each push/pop step: the orange highlight is the current vertex, the gold path is the partial circuit, and faded edges are already used.

Key takeaway: Hierholzer = stack-based DFS over edges; linear time, very simple to implement, and produces a complete Eulerian circuit.
🌍Applied Where does graph theory show up in the real world?▶

Almost everywhere. Networks: routing in the internet (shortest paths), social network analysis, recommendation systems. Map coloring: scheduling and frequency assignment use coloring to avoid conflicts; the four color theorem guarantees four cellular frequencies suffice for planar territories. Routing: postal-route optimization is the Chinese Postman Problem — find shortest closed walk traversing every edge (an Eulerian relaxation). The Travelling Salesman Problem is the Hamiltonian relaxation with edge weights. Compilers: register allocation is graph coloring on the interference graph of variables. Logistics: vehicle routing, garbage collection routing. Bioinformatics: DNA sequencing assembles overlapping fragments using Eulerian paths in De Bruijn graphs — modern genome assemblers all use this. Linguistics: dependency graphs in NLP. Quantum chemistry: graph isomorphism for molecular structure.

Key takeaway: routing, scheduling, register allocation, DNA assembly, social networks — all rely on graph algorithms.
💡Non-Obvious Why is the Petersen graph NOT Hamiltonian, despite being 3-regular?▶

The Petersen graph has 10 vertices, every vertex has degree 3 — it's vertex-transitive, looks symmetric, and "feels" like it should have a Hamiltonian cycle. It doesn't. Sketch: suppose it does. The graph is bipartite-like in structure with an outer pentagon $\{0,1,2,3,4\}$ connected to an inner pentagram $\{5,6,7,8,9\}$. A Hamiltonian cycle uses 10 edges total; counting how many cross between outer and inner — by parity it must be even, and arguments about the pentagram structure force a contradiction. The Petersen graph is the smallest 3-regular graph that is non-Hamiltonian, and the canonical counterexample for many graph-theoretic conjectures. Its non-Hamiltonicity also implies it cannot be "edge-decomposed" into perfect matchings in a particular way.

Key takeaway: high regularity ≠ Hamiltonian. The Petersen graph is the standard example showing global structure matters.
📐Computational What's the chromatic number of a random graph?▶

For an Erdős–Rényi random graph $G(n, p)$ with constant edge probability $p$, Bollobás (1988) proved $\chi(G(n,p)) \sim \dfrac{n}{2\log_b n}$ where $b = 1/(1-p)$, with high probability. For $p=1/2$: $\chi \sim n/(2\log_2 n)$. For $n=100$ and $p=0.5$, expect $\chi \approx 100/(2\cdot 6.6) \approx 7.5$, so 7 or 8 colors. Greedy coloring (Welsh–Powell) typically uses about twice the optimum for random graphs. Exact $\chi$ is NP-hard to compute, but practical solvers (DSATUR, integer programming) handle hundreds of vertices. The simulation displays the greedy upper bound — exact $\chi$ for the displayed graph is shown only for small instances where exhaustive search is tractable.

Key takeaway: $\chi$ of random graphs is $\sim n/(2\log n)$; computing it exactly is NP-hard but practical for $n \lesssim 200$.
🎓Deep / Advanced What's the relationship between graph coloring and other branches of math?▶

Coloring is surprisingly central. Chromatic polynomial $P(G, k)$ counts proper $k$-colorings; it satisfies a deletion-contraction recurrence and has connections to the Tutte polynomial, knot theory (Jones polynomial via Tait colorings), and statistical mechanics (Potts model partition functions). Topological obstructions: the four color theorem is intimately connected to planarity — embeddability in $\R^2$. The Hadwiger conjecture proposes $\chi(G) \le t$ whenever $G$ contains no $K_{t+1}$ minor — a dramatic generalization. Algebraic graph theory: $\chi(G) \leq 1 + \lambda_{\max}(\text{adjacency})$ (Wilf's bound) and $\chi(G) \geq n/(n - \lambda_{\min})$ (Hoffman), tying coloring to spectral graph theory. Probabilistic combinatorics: random colorings via Lovász Local Lemma. Computer science: register allocation, exam scheduling, Sudoku-as-coloring, all NP-hard variants.

Key takeaway: graph coloring connects topology, spectral theory, knot theory, and statistical physics — far more than just "color the map".
🧮Conceptual Is a graph the same as its drawing on the plane?▶

No — a graph is an abstract combinatorial object: a set $V$ and a set of pairs $E \subseteq \binom{V}{2}$. The drawing is just a visual representation. Two completely different-looking drawings can represent the same graph (graph isomorphism). Whether a graph can be drawn without edge crossings in the plane is a separate property called planarity (Kuratowski's theorem: $G$ is planar iff it contains no $K_5$ or $K_{3,3}$ minor). The simulation lets you drag vertices: you're just moving the drawing — the graph (vertex set, edge set) stays the same. Two graphs are equal iff they have the same vertex set and edge set; isomorphic if there's a relabeling that makes them equal.

Key takeaway: graphs are combinatorial; drawings are just one way to see them. Planarity is about whether some crossing-free drawing exists.
Best resource: 3Blue1Brown — "How they found the world's biggest prime number" (touches on graph algorithms); MIT OCW 6.042J — Mathematics for Computer Science, Lectures 11–14; Khan Academy — Algorithms; Wolfram MathWorld — Eulerian Path, Hamiltonian Path, Chromatic Number; Brilliant.org — Graph Theory; Graph Theory with Applications (Bondy & Murty 1976, free PDF online).

⚠️ Section 5 — Misconceptions & Common Errors

A · Conceptual Misconceptions
❌ Misconception: "Eulerian and Hamiltonian are basically the same — both are about traversing a graph." ✅ Correction: Different objects: Eulerian uses every edge exactly once; Hamiltonian visits every vertex exactly once. Different difficulty: Eulerian has a $O(\abs{E})$ algorithm and a clean degree-parity characterization; Hamiltonian is NP-complete with no such characterization. Different examples: cycle $C_n$ is both; complete graph $K_n$ is both for $n \geq 3$ odd, only Hamiltonian for $n$ even (since $K_n$ has all degrees $n-1$, which is odd when $n$ is even); the Petersen graph is neither Eulerian (all degrees are 3, which is odd) nor Hamiltonian. 📖 Reference: West — Introduction to Graph Theory, 2nd ed., §1.2 (Euler) vs §7.2 (Hamilton).
❌ Misconception: "If $G$ has a vertex of degree $n-1$, it's Hamiltonian." ✅ Correction: One high-degree vertex is not enough. The "star" graph $K_{1,n-1}$ has one center vertex connected to $n-1$ leaves; the center has degree $n-1$, but there's no Hamiltonian cycle (any cycle would need each leaf to have two cycle-neighbours, but leaves have degree 1). Dirac's condition requires every vertex to have $\deg \geq n/2$. Ore's condition is similar — pairs of non-adjacent vertices must collectively have degree at least $n$. 📖 Reference: Bondy & Murty — Graph Theory, Springer GTM 244, Ch. 4 (Hamiltonicity).
❌ Misconception: "Greedy coloring with Welsh–Powell always gives the chromatic number $\chi(G)$." ✅ Correction: Greedy gives an upper bound, not necessarily the optimum. There exist graphs (the "anti-greedy" examples) where Welsh–Powell uses arbitrarily many more colors than $\chi$. Determining $\chi$ exactly is NP-hard. For random graphs the greedy bound is asymptotically tight up to a constant factor of 2, but on specific instances it can be far from optimal. Best practice: combine greedy bounds with lower bounds (e.g., $\chi \geq \omega(G)$, the clique number) to sandwich $\chi$. 📖 Reference: Diestel — Graph Theory, 5th ed., Ch. 5 §5.1 (greedy bounds and counterexamples).
B · Common Procedural Errors
❌ Error: "Sum of degrees in a graph: $\sum_{v} \deg(v) = \abs{E}$." ✅ Correct: Each edge contributes $2$ to the degree sum (once for each endpoint), so $\boxed{\sum_v \deg(v) = 2\abs{E}}$ — the handshake lemma. Corollary: the number of odd-degree vertices is always even (since the sum is even, the odd contributions must pair up). The student is off by a factor of 2 — this leads to wrong answers in any "given degree sequence, count edges" problem. 🔍 Why students do this: forget that an edge has two endpoints, count its contribution once instead of twice.
❌ Error: "$K_4$ has 4 vertices and 4 edges." ✅ Correct: The complete graph $K_n$ has $\binom{n}{2} = n(n-1)/2$ edges — every pair of vertices is connected. So $K_4$ has $\binom{4}{2} = 6$ edges, not 4. (4 edges would form a cycle $C_4$.) Justifying rule: in the complete graph, choose any 2 of the $n$ vertices for an edge — that's $\binom{n}{2}$ choices. Quick check: the handshake formula gives $\sum \deg = 4 \cdot 3 = 12 = 2 \cdot 6$, confirming 6 edges. 🔍 Why students do this: confuse $K_n$ (complete) with $C_n$ (cycle); both have $n$ vertices but very different edge counts.
❌ Error: "If $G$ has $k$ connected components, the number of edges is at most $n - k$." ✅ Correct: The bound $n - k$ is for spanning forests (acyclic edge-minimal connected-component subgraphs), not for $G$. A graph $G$ with $k$ components and no other constraint can have up to $\sum_i \binom{n_i}{2}$ edges where $n_i$ is the size of each component. In a tree (one component, no cycles), edges $= n - 1$. In a forest with $k$ trees, edges $= n - k$. But any graph can have many more edges if it contains cycles. 🔍 Why students do this: confuse the tree formula $\abs{E} = n-1$ with the general edge count, which has no simple component-based formula.
Education research: Hazzan, O. & Hadar, I. — "Reducing abstraction when learning graph theory", Journal of Computers in Mathematics and Science Teaching 24(3), 255–272 (2005); Ferrarello, D. & Mammana, M. F. — "Graph theory in primary, middle, and high school", ICME-13 Topical Surveys (2018); Kasman, R. — "Critical mathematics education and graph theory", Mathematics Teaching in the Middle School (2010); Medová, J. et al. — "Computational thinking and discrete mathematics: graph theory in school education", Journal of Computer Assisted Learning (2019).