Almost too good to be true. But they proved it.

In 2004, Jeong Han Kim and Van H. Vu proposed something that sounded almost too convenient. Take two kinds of random graphs. The binomial model \(G(n,p)\) has edges that appear independently. The random regular graph \(G_d(n)\) gives every vertex exactly the same number of neighbors. The second is harder to study. The first has decades of theorems built for it.

Kim and Vu suggested that a random regular graph could be sandwiched between two binomial graphs on the same vertex set:

$$G_* \subseteq G \subseteq G^*$$

The statement was brief. The proof took about twenty years.

In 2025, the conjecture was proved by Natalie Behague, Daniel Iľkovič, and Richard Montgomery, mathematicians at the University of Warwick's Mathematics Institute; Iľkovič is also affiliated with Leipzig University. Montgomery announced the result in September 2025 at the Oberwolfach Research Institute for Mathematics in Germany. The preprint was posted on arXiv on October 23, 2025; a second version appeared on December 8, 2025.

In an interview published by Quanta Magazine on September 18, 2026, Behague described the connection between the two models as "almost too good to be true."

Both models can produce graphs with approximately the same number of edges. The rules differ.

In \(G(n,p)\), each possible edge appears independently with probability \(p\). No vertex has a fixed quota. In a random \(d\)-regular graph, every vertex has exactly \(d\) neighbors. Choosing one edge affects which edges can be added next. You cannot simply add connections at random: some vertices may reach their allotted \(d\) neighbors too early. And every admissible \(d\)-regular graph must be produced with the same probability, or the selection is biased.

The sandwich requires more than containment. The three graphs must be constructed jointly — a coupling — so that each retains its own distribution. The marginal distribution of \(G\) must remain that of a uniformly chosen \(d\)-regular graph. The outer layers must retain their binomial distributions.

The theorem places a restriction on the degree \(d\). The upper binomial graph can contain a \(d\)-regular graph only if each of its vertices has at least \(d\) neighbors. In \(G(n,p)\), the number of connections fluctuates around the mean. When the graph is too sparse, at least one vertex will have fewer than \(d\) neighbors. The regular graph then cannot fit inside.

For a sandwich with a vanishingly small relative gap, this obstacle disappears when \(d\) grows faster than \(\log n\):

$$d = \omega(\log n), \quad \text{that is,} \quad d/\log n \to \infty$$

The quantitative statement also includes \(d \ge C \log n\), with \(C = C(\varepsilon)\) depending on the allowed relative deviation \(\varepsilon\).

Mathematicians gradually expanded the range of \(d\).

- Kim and Vu proved the lower inclusion over part of the range and obtained a weakened upper inclusion.

- In 2017, Dudek, Frieze, Ruciński, and Šileikis extended the range for the lower inclusion.

- Pu Gao, Mikhail Isaev, and Brendan McKay obtained the first full sandwich for denser random regular graphs and later reached \(d \gg \log^4 n\).

Between \(\log n\) and \(\log^4 n\) lay a large range the earlier analysis did not cover. The hardest part remained the upper inclusion \(G \subseteq G^*\).

The coupling procedure was introduced in earlier work by Gao, Isaev, and McKay. The new proof develops its analysis through estimates for switching paths.

Two coupling processes run in opposite directions. The addition process starts from an empty graph and accepts edges, giving an edge a lower chance of acceptance if it reduces the number of possible regular completions too sharply. The deletion process starts from the complete graph and proposes edges for deletion, with the probability of deleting an edge \(e\) given by:

$$a_e(F) = \frac{N_d(F - e)}{\max_{f \in E(F)} N_d(F - f)}$$

The numerator is the number of spanning \(d\)-regular subgraphs that survive the deletion of \(e\); the denominator is the largest such number among all deletable edges at that step. If deleting \(e\) would destroy all regular backbones, the numerator is zero, and the edge stays.

The two processes differ in their number of steps. A \(d\)-regular graph has exactly \(nd/2\) edges. The complete graph contains \(n(n-1)/2\) possible edges, a quantity of order \(n^2\), so the deletion process can involve far more steps. Even a small error can accumulate. The authors adjust the required accuracy as the process proceeds and control the total error.

Counting all possible regular backbones directly is impossible. Instead, the authors use switching — a technique that compares entire families of graphs without examining them all.

The simplest switching replaces edges \(AB\) and \(CD\) with \(AD\) and \(BC\). Each of the four vertices loses one edge and gains one, so its degree is preserved. Each transition connects exactly one graph in one family with one graph in another.

In a small example: if the first family contains 100 graphs, each with four admissible switchings leading out, there are 400 transitions. If each graph in the second family has five reverse transitions, that family must contain 80 graphs, since \(100 \times 4 = 80 \times 5\).

In a sparse graph, the required parts for a four-vertex switching may lie far apart. The authors then use longer alternating paths. Starting from a chosen vertex, the first step along an extra edge offers approximately \(\delta\) choices, and the next step along a backbone edge offers about \(d\). Two successive steps give approximately \(\delta d\) possible continuations. Repeating this pair of steps \(\ell\) times gives the rough estimate:

$$(\delta d)^{\ell} / n$$

Sparsity makes this count sensitive to small errors. If the number of continuations is overestimated by just 1% one hundred times in a row, the overall error factor becomes approximately \(1.01^{100} \approx 2.7\). The authors therefore track successive neighborhoods to prevent local errors from accumulating.

The result links two random graph models almost down to the natural logarithmic boundary. A uniformly random \(d\)-regular graph can be coupled with two binomial graphs of nearly the same density so that \(G_* \subseteq G \subseteq G^*\) holds with probability tending to one.

This allows results on connectivity, Hamiltonian cycles, coloring, and other suitable properties proved for \(G(n,p)\) to be transferred to random regular graphs through inclusion.

In July 2026, a paper by Mikhail Isaev and coauthors on the canonical labeling of random regular graphs received the best paper award for Track A at the ICALP conference. That work invokes the sandwich theorem to estimate edge counts between vertex sets in its treatment of dense random regular graphs.

Behague, Iľkovič, and Montgomery also formulate a conjecture. They propose coupling a single \(d\)-regular graph with an entire random process in which one randomly selected missing edge is added at each step, starting from \(n\) isolated vertices. They conjecture that, with high probability, the containment conditions hold simultaneously at every step.

That remains unproven, and the authors note it will likely require fundamentally new ideas.

So: a twenty-year-old conjecture, proved almost down to the logarithmic threshold, with a new conjecture already sitting on the table. Mathematics, as usual, does not pause to celebrate.