# Graph theory

> 40 AI-made results on graph theory, each explained in plain English. A graph is a set of dots joined by lines. Graph theory studies colourings, cycles…

Canonical: https://closedform.nishachay.tech/topic/graph-theory/
Last updated: 2026-10-14

A graph is a set of dots joined by lines. Graph theory studies colourings, cycles and patterns in these networks.

40 AI-made results on graph theory, from 67 papers in the OpenAI math collection, each explained in plain English. 33 have a formal Lean proof listed; 7 are claimed in a paper and not yet machine-checked. They span 8 fields, led by combinatorics (21), theoretical computer science (7) and probability and statistical mechanics (4). The oldest question here dates back to 1935: [Sharp logarithmic exponents for off-diagonal Ramsey numbers](https://closedform.nishachay.tech/e/openai-math-2026-170/). Results rated Landmark include [The Unique Games Conjecture and optimal approximation thresholds](https://closedform.nishachay.tech/e/openai-math-2026-102/) and [Graph coloring, clique minors, and Colin de Verdière invariants](https://closedform.nishachay.tech/e/openai-math-2026-157/).

## Results (40)

- [Uniformly bounded components of Gaussian-prime graphs](https://closedform.nishachay.tech/e/openai-math-2026-028/) - Entry 028 · No walk through Gaussian primes with steps of bounded length can go on forever. (Formal proof listed)
- [Bounded-distortion L 1 embeddings of planar and bounded-treewidth graphs](https://closedform.nishachay.tech/e/openai-math-2026-089/) - Entry 089 · Every planar road network can be redrawn in taxicab distance with stretch below one fixed number. (Formal proof listed)
- [The Unique Games Conjecture and optimal approximation thresholds](https://closedform.nishachay.tech/e/openai-math-2026-102/) - Entry 102 · Telling almost-solvable puzzles from hopeless ones can be impossibly hard. (Formal proof listed)
- [Hardness of coloring three-colorable graphs](https://closedform.nishachay.tech/e/openai-math-2026-106/) - Entry 106 · Even a three-colorable graph can be NP-hard to tell from one with only tiny independent sets. (Formal proof listed)
- [Approximate counting and entropy of perfect matchings](https://closedform.nishachay.tech/e/openai-math-2026-113/) - Entry 113 · A fast coin-flipping method estimates the number of perfect matchings in any network, to any chosen accuracy. (Formal proof listed)
- [Almost-linear-time exact matching and prescribed-degree factors in general graphs](https://closedform.nishachay.tech/e/openai-math-2026-120/) - Entry 120 · A randomized algorithm finds a largest matching in any graph in almost-linear time, the paper claims. (Claimed, not checked)
- [Polynomial-time scheduling on three identical machines](https://closedform.nishachay.tech/e/openai-math-2026-124/) - Entry 124 · The best schedule for one-hour jobs with order rules on three machines can be found in polynomial time. (Formal proof listed)
- [Rapid mixing of graph switches for every degree sequence](https://closedform.nishachay.tech/e/openai-math-2026-131/) - Entry 131 · Random rewiring reaches a fair random network quickly, for every possible list of degrees. (Formal proof listed)
- [The computational complexity of Weisfeiler–Leman refinement](https://closedform.nishachay.tech/e/openai-math-2026-133/) - Entry 133 · Deciding Weisfeiler–Leman equivalence at dimension k needs time n to a power proportional to k. (Formal proof listed)
- [Graph coloring, clique minors, and Colin de Verdière invariants](https://closedform.nishachay.tech/e/openai-math-2026-157/) - Entry 157 · Proves Hadwiger's 1943 coloring conjecture is false, and that a fixed multiple of the minor size still bounds coloring. (Formal proof listed)
- [The Euclidean plane cannot be colored with five colors](https://closedform.nishachay.tech/e/openai-math-2026-158/) - Entry 158 · No way of coloring the plane with five colors keeps every unit-distance pair apart. (Formal proof listed)
- [Superexponential van der Waerden numbers](https://closedform.nishachay.tech/e/openai-math-2026-160/) - Entry 160 · Proves van der Waerden numbers grow faster than any exponential, answering a question of Erdős for two colors. (Formal proof listed)
- [Counterexamples to Sidorenko’s conjecture and the forcing conjecture](https://closedform.nishachay.tech/e/openai-math-2026-161/) - Entry 161 · A 35-vertex bipartite pattern appears less often in some graph than random would predict. (Formal proof listed)
- [Counterexamples to Ryser’s covering conjecture](https://closedform.nishachay.tech/e/openai-math-2026-162/) - Entry 162 · Ryser's covering conjecture is false: some intersecting hypergraphs with r parts need r vertices to cover. (Formal proof listed)
- [The Harary–Hill and Zarankiewicz crossing-number formulas](https://closedform.nishachay.tech/e/openai-math-2026-165/) - Entry 165 · The classic crossing formulas for drawing complete networks are exact. (Formal proof listed)
- [Shareshian–Wachs elementary positivity](https://closedform.nishachay.tech/e/openai-math-2026-169/) - Entry 169 · A coloring count with an extra q-weight always splits into elementary pieces with nonnegative coefficients. (Formal proof listed)
- [Sharp logarithmic exponents for off-diagonal Ramsey numbers](https://closedform.nishachay.tech/e/openai-math-2026-170/) - Entry 170 · For every fixed s ≥ 5, the Ramsey number r(s,t) now has its exact power of log t, up to a vanishing error. (Formal proof listed)
- [The hypercube Ramsey conjecture](https://closedform.nishachay.tech/e/openai-math-2026-171/) - Entry 171 · Two-coloring the links among a constant times 2ⁿ points always gives a one-color n-dimensional cube, the paper claims. (Claimed, not checked)
- [Classification of finite Euclidean Ramsey configurations](https://closedform.nishachay.tech/e/openai-math-2026-172/) - Entry 172 · An exact algebraic test tells which finite point sets must appear in one color in any coloring of space. (Formal proof listed)
- [Seymour’s second-neighborhood conjecture](https://closedform.nishachay.tech/e/openai-math-2026-173/) - Entry 173 · In every network of one-way arrows, some point reaches at least as many points in two steps as in one. (Formal proof listed)
- [Talagrand’s expectation thresholds, discrete convexity, and graph decompositions](https://closedform.nishachay.tech/e/openai-math-2026-175/) - Entry 175 · Spreading credit fractionally beats whole-set covers by at most a fixed factor in Talagrand's threshold theory. (Formal proof listed)
- [The second Kahn–Kalai conjecture with an edge-count bound](https://closedform.nishachay.tech/e/openai-math-2026-176/) - Entry 176 · A random graph contains a target graph soon after simple expected counts say it could, up to a log factor. (Formal proof listed)
- [Bounded-degree coboundary expanders](https://closedform.nishachay.tech/e/openai-math-2026-177/) - Entry 177 · Large higher-dimensional expanders with a bounded number of faces at each point exist in every dimension. (Formal proof listed)
- [Deterministic nonbipartite Ramanujan graphs in every fixed degree](https://closedform.nishachay.tech/e/openai-math-2026-178/) - Entry 178 · A fixed recipe builds networks with best-possible mixing, in every degree and every large even size. (Claimed, not checked)
- [Barnette’s Hamiltonian-cycle conjecture](https://closedform.nishachay.tech/e/openai-math-2026-180/) - Entry 180 · Every Barnette graph has a round trip through all its points. (Formal proof listed)
- [The Erdős–Gallai cycle-decomposition conjecture](https://closedform.nishachay.tech/e/openai-math-2026-181/) - Entry 181 · Every network on n points splits into at most a fixed multiple of n loops and single links. (Formal proof listed)
- [Correspondence coloring with a fixed forbidden subgraph](https://closedform.nishachay.tech/e/openai-math-2026-184/) - Entry 184 · Networks with no fixed-size clique have larger independent sets and need fewer colors, by a log factor. (Formal proof listed)
- [Uniform influence and sharp thresholds for graph and hypergraph properties](https://closedform.nishachay.tech/e/openai-math-2026-186/) - Entry 186 · Every symmetric increasing graph property switches on within a window of width about 1/(log n)². (Formal proof listed)
- [The sharp terminal leave in random triangle removal](https://closedform.nishachay.tech/e/openai-math-2026-188/) - Entry 188 · Randomly erasing triangles from a complete graph leaves about n^(3/2)/(2√2) edges at the end. (Formal proof listed)
- [Cycle–clique Ramsey numbers](https://closedform.nishachay.tech/e/openai-math-2026-189/) - Entry 189 · Exact Ramsey numbers for a cycle versus a clique: R(C_m, K_n) = (m − 1)(n − 1) + 1 when m ≥ n ≥ 3. (Formal proof listed)
- [Critical percolation on every quasi-transitive graph](https://closedform.nishachay.tech/e/openai-math-2026-213/) - Entry 213 · At the exact tipping point, random networks of a broad, symmetric kind form no endless cluster. (Formal proof listed)
- [The Benjamini–Schramm nonuniqueness conjecture](https://closedform.nishachay.tech/e/openai-math-2026-214/) - Entry 214 · Percolation on every fast-spreading symmetric graph has a range with infinitely many endless clusters. (Formal proof listed)
- [GOE bulk universality for regular graphs with weak Anderson disorder](https://closedform.nishachay.tech/e/openai-math-2026-219/) - Entry 219 · Eigenvalue spacings of random regular graphs, even with weak random potentials, match those of Gaussian random matrices. (Claimed, not checked)
- [The free uniform spanning forest is a factor of IID](https://closedform.nishachay.tech/e/openai-math-2026-231/) - Entry 231 · One fixed rule builds the free uniform spanning forest from independent random labels on every infinite graph. (Formal proof listed)
- [QAOA attains the SK optimum in the thermodynamic-first limit](https://closedform.nishachay.tech/e/openai-math-2026-281/) - Entry 281 · Claims QAOA reaches the Sherrington–Kirkpatrick ground-state energy as size grows first and depth then increases. (Formal proof listed)
- [Failure of rational injectivity for maximal coarse assembly](https://closedform.nishachay.tech/e/openai-math-2026-307/) - Entry 307 · Graph families where coarse assembly forgets a class of infinite order; Lean checks the reduced version. (Formal proof listed)
- [Cyclic length and chromatic fixed-point loss](https://closedform.nishachay.tech/e/openai-math-2026-314/) - Entry 314 · Claims the exact chromatic loss between fixed points of p-group actions is a count of cyclic steps. (Claimed, not checked)
- [Chromatic splitting: filtrations and counterexamples](https://closedform.nishachay.tech/e/openai-math-2026-318/) - Entry 318 · Five papers claim Hopkins' chromatic splitting conjecture fails in its strong and weak forms, and offer a filtered fix. (Claimed, not checked)
- [Counterexamples to finite generation at chromatic height two](https://closedform.nishachay.tech/e/openai-math-2026-319/) - Entry 319 · A paper claims to disprove the Hahn–Wilson conjecture at height two, for every large enough prime. (Claimed, not checked)
- [Affine Bernstein rigidity through dimension nine and a smooth dimension-ten counterexample](https://closedform.nishachay.tech/e/openai-math-2026-353/) - Entry 353 · Proves affine Bernstein rigidity for complete graphs in dimensions 3 to 9; claims a smooth dimension-ten counterexample. (Formal proof listed)

## Related

- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Open since the 1990s](https://closedform.nishachay.tech/open-since/1990s/) - Era · 55 results
- [Claimed, not yet checked](https://closedform.nishachay.tech/trust/claimed/) - Trust · 130 results
- [Open since the 1960s](https://closedform.nishachay.tech/open-since/1960s/) - Era · 33 results
- [Erdős problems](https://closedform.nishachay.tech/topic/erdos-problems/) - Topic · 13 results
- [Named conjectures](https://closedform.nishachay.tech/topic/named-conjectures/) - Topic · 85 results
- [Ramsey theory](https://closedform.nishachay.tech/topic/ramsey-theory/) - Topic · 5 results
- [Prime numbers](https://closedform.nishachay.tech/topic/prime-numbers/) - Topic · 12 results
- [Distances and packing](https://closedform.nishachay.tech/topic/distances-and-packing/) - Topic · 5 results
- [Curvature and geometric flows](https://closedform.nishachay.tech/topic/curvature-and-geometric-flows/) - Topic · 17 results
- [Combinatorics](https://closedform.nishachay.tech/science/mathematics/combinatorics/) - Field · 21 here
- [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 7 here
- [Probability and statistical mechanics](https://closedform.nishachay.tech/science/mathematics/probability-and-statistical-mechanics/) - Field · 4 here
- [All topics](https://closedform.nishachay.tech/topics/) - Every way to browse