A Bit of History
Graph theory's open problems are frequently far easier to state than the machinery needed to solve them — a running theme across this entire series, from the Four Color Theorem's century-long wait (Part 13) to the still-unresolved gap between the best-known Ramsey number bounds (Part 19). This closing part surveys a handful of the field's most famous remaining open questions, and offers concrete guidance for continuing to learn and eventually contribute to the field beyond this series.
The Hadwiger Conjecture
Proposed by Hugo Hadwiger in 1943, this conjecture generalizes the Four Color Theorem dramatically: it claims that any graph with no \(K_{t+1}\) minor (recall minors from Part 17 and Part 18) can be colored with at most \(t\) colors. For \(t=4\), this is exactly equivalent to the Four Color Theorem (since planar graphs are precisely those with no \(K_5\) minor, by Wagner's theorem). The conjecture remains open for all \(t \geq 6\), despite being provable for small cases and being widely regarded — partly due to its Robertson-Seymour-adjacent minor-theoretic flavor — as one of the deepest open problems connecting coloring and structural graph theory.
The Reconstruction Conjecture
Proposed independently around 1941 by Paul Kelly and Stanislaw Ulam, this conjecture asks: if you are given the complete multiset of subgraphs obtained by deleting each single vertex from a graph one at a time (its "deck" of vertex-deleted subgraphs), can the original graph always be uniquely reconstructed from that deck alone (for graphs with at least 3 vertices)? This deceptively simple-sounding question about "can the whole be recovered from all its almost-whole pieces" remains unresolved after more than 80 years, verified computationally for many specific graph families but never proven in full generality.
Why These Problems Persist
Both the Hadwiger and Reconstruction conjectures share a pattern seen repeatedly across this series' history sections: verified true in every specific case anyone has ever checked, yet resistant to a fully general proof — precisely the gap between overwhelming empirical evidence and rigorous mathematical certainty that makes these problems simultaneously frustrating and irresistible to researchers.
Other Open Problems Revisited
Several open questions already appeared earlier in this series and are worth revisiting together as a reminder of how much remains unsettled:
- P vs. NP (Part 22) — does every NP-complete graph problem (Hamiltonian Cycle, Graph Coloring, Clique) secretly admit a polynomial-time algorithm?
- Exact Ramsey numbers (Part 19) — even \(R(5,5)\) remains genuinely unknown, pinned only between 43 and 46.
- The graph isomorphism problem's exact complexity (Part 18) — Babai's 2015 quasipolynomial algorithm narrowed the gap, but whether a true polynomial-time algorithm exists is still open.
How to Read a Graph Theory Paper
A practical skill this series has modeled implicitly throughout: every algorithm deep dive traced a paper's history, stated its core theorem precisely, and worked through a small example before touching implementation. Reading real research papers rewards the same discipline — start with the abstract and introduction to understand what problem is being solved and why it matters, skip ahead to skim the main theorem statement before working through the proof, and always try a tiny concrete example by hand before trusting you've understood a general construction.
Where Research Happens
Modern graph theory and algorithms research is published across several distinct venues, each with its own culture: theoretical computer science conferences like STOC (Symposium on Theory of Computing), FOCS (Foundations of Computer Science), and SODA (Symposium on Discrete Algorithms) are where many of the algorithms in this series (Hopcroft-Karp, Micali-Vazirani, Karger-Stein) were first presented; pure mathematics journals carry structural results like the Robertson-Seymour graph minors series; and the open-access preprint server arXiv.org now hosts early versions of nearly all of this research well before formal peer-reviewed publication, making cutting-edge results freely and immediately accessible to anyone.
Real-World Applications
The Erdős Number: A Playful Case Study in Collaboration Graphs
Mathematicians jokingly track their "Erdős number" — the collaboration-graph distance (co-authorship as an edge) between themselves and Paul Erdős, whose name has appeared throughout this series (Ramsey theory, the probabilistic method, random graphs) as one of history's most prolific and collaborative mathematicians. This lighthearted tradition is itself a small, real-world application of the shortest-path algorithms from Parts 9-10, computed over an actual co-authorship graph spanning hundreds of thousands of mathematicians — proof that even a field's internal culture can become a graph theory exercise.
Exercises
- Explain why the Hadwiger Conjecture for \(t=4\) is exactly equivalent to the Four Color Theorem, using Wagner's minor-based planarity characterization from Part 17.
- Construct the "deck" of vertex-deleted subgraphs for a small graph (e.g., a 4-vertex path), and verify by inspection that the original graph could plausibly be reconstructed from that deck.
- Pick any algorithm deep dive from this series and identify which of the three research venues (STOC/FOCS/SODA, a math journal, or arXiv) its original paper was most likely published in, based on its style and content.
- Challenge: Choose one specific open problem from this part (Hadwiger, Reconstruction, exact Ramsey numbers, or graph isomorphism complexity) and locate a recent (last 5 years) arXiv paper making partial progress on it, summarizing what progress was made.
Conclusion: Thank You for Reading
This series began with sets, logic, and proof techniques — the bedrock every later theorem rested on — and has now traveled through traversal, shortest paths, trees, flows, coloring, planarity, structural theory, probability, spectral methods, complexity, modern scalable algorithms, richer network structures, network science, machine learning, scientific applications, and finally the field's open frontiers. Twenty-eight parts and twenty-eight algorithm deep dives later, graph theory remains — as it has been since Euler first crossed the bridges of Königsberg in 1736 — a field where the simplest possible questions ("can I draw this without lifting my pen," "how many colors do I need," "who is connected to whom") continue to open onto genuinely deep, sometimes still-unsolved mathematics. Thank you for following the whole journey.