Science 1 publisher2 min readPublished September 18, 2026 at 8:10 AM PDT

Random regular graphs can now inherit their properties from the easier random model

The sandwich conjecture that Jeong Han Kim and Van Ha Vu posed in 2004 was proved in 2025, so a property established for a random binomial graph now carries to the regular graph containing it, once the graph is large enough.

The Scientist · Science desk

What happened

Jeong Han Kim and Van Ha Vu proposed in the early 2000s that a random regular graph could be approximated by a random binomial graph, and in 2004 the pair set the idea out as a conjecture.
Three mathematicians completed the proof in 2025, after two decades in which the field produced partial results but nobody closed the full statement.
The difficulty being routed around is real: after the Hamiltonian cycle question was settled for binomial graphs, the same question for regular graphs took another 20 years of work.
The binomial model dates to the late 1950s, when Edgar Gilbert built it at Bell Labs to study telephone networks and Erdos and Renyi arrived at something similar independently.

Compiled by The ScientistSomething wrong?How this is made

Why it matters

capability A property that resists direct attack on random regular graphs can be imported from the binomial model instead of proved again from scratch. The Hamiltonian cycle history shows the size of the saving.
constraint The guarantee is asymptotic. It binds only graphs that are large enough, which leaves anyone holding one network of a fixed vertex count outside its reach.
decision A researcher needing a result about random regular graphs now chooses between working in the constrained model directly and proving the statement in the binomial model, then invoking the sandwich.
precedent The proof establishes that two very different random processes are linked more closely than the field assumed. Similar transfer results between other pairs of random models become a reasonable thing to look for.

The construction is a single random process that builds a binomial graph and a regular graph at the same time, arranged so the two fit together in a particular way ^[5]. One half of the fit is a containment: the recipe has to hand you a regular graph whose edge set includes every edge of the binomial graph ^[6]. When it does, results proved about the binomial graph also hold for the regular one ^[7]. Quanta describes the full requirement as layering the cheese onto each slice of bread separately, so the containment has to be arranged twice ^[8].

The obstacle all along was structural. In a regular graph every vertex has the same number of edges, and those edges form more constrained, interdependent patterns than a coin flip per pair produces ^[18]^[9]^[22]. Hamiltonian cycles are one measure of what that costs: conditions for a binomial graph were in hand by the 1970s ^[10], and the regular-graph answer took another 20 years of work ^[11], which puts it in roughly the 1990s ^[12].

Pu Gao, a mathematician at the University of Waterloo who has worked on the problem, told Quanta the pull was aesthetic ^[16]. "The notion is so beautiful," Gao said ^[14]. "What attracts me most is actually the beauty of it" ^[15].

The theorem moves proofs between two idealized models. Quanta says random regular graphs are often much more accurate at modeling real-world networks than binomial ones ^[18]; the sandwich carries a statement from the binomial model into the regular model, and it does not test either against a measured network. The guarantee is also conditional on size, since the conjecture holds so long as the graph you care about is large enough, and the account does not state a threshold ^[3]^[20].

Within those conditions, the payoff is the one Kim and Vu were after in the early 2000s: many hard-to-prove properties of a regular graph come from the matching binomial graph for free ^[2]^[19]. Twenty-one years passed between the conjecture and the proof ^[13].

What to watch

Whether the published 2025 proof puts a number on large enough.
The first papers that cite the sandwich to claim a random regular graph property without reproving it.
Which degree ranges the completed theorem covers, since that fixes which regular graphs the transfer reaches.

Claim ledger

Ranked by verification strength, evidence, and original report placement.

[4]
Over the past two decades mathematicians made progress on the sandwich conjecture but no one could prove it in full; in 2025 three mathematicians found a way to push their field's techniques to their limits and completed the quest.
ReportedSupported2 sources— sign in to open View cited source
[1]
In 2004, two mathematicians hypothesized a powerful kind of graph sandwich, aiming to understand a hard-to-analyze type of graph by sandwiching it rigorously between two simpler graphs.
ReportedSupportedView cited source
[2]
In the early 2000s, Jeong Han Kim, then at Microsoft Research, and Van Ha Vu, then at the University of California, San Diego, showed how to approximate random regular graphs with random binomial graphs by making a graph sandwich.
ReportedSupportedView cited source
[3]
The sandwich conjecture says that so long as the graph you are interested in is large enough, you can always create the needed sandwich.
ReportedSupportedView cited source
[5]
The idea was to find a single recipe, a random process, that builds a binomial graph and a regular graph at the same time, generating the right kinds of graphs and making them fit together in just the right way.
ReportedSupportedView cited source
[6]
First, you need a recipe that gives you a regular graph that contains a binomial graph, meaning the binomial graph's edges form a subset of the edges making up the regular graph.
ReportedSupportedView cited source
[7]
If you can build the sandwich, then when you prove results about the binomial graph, which is relatively easy to analyze, those results will also hold for the regular graph.
ReportedSupportedView cited source
[8]
Quanta's account states that you have to come up with a recipe that layers the cheese on each slice of bread separately.
ReportedSupportedView cited source
[9]
Random regular graphs are much harder to analyze than binomial graphs because their edges form more constrained, interdependent patterns.
ReportedSupportedView cited source
[10]
By the 1970s mathematicians had discovered under what conditions a random binomial graph will contain a Hamiltonian cycle, a path that visits each vertex exactly once.
ReportedSupportedView cited source
[11]
It took an additional 20 years of work after the Hamiltonian cycle question was answered for binomial graphs before mathematicians could answer it for regular graphs.
ReportedSupportedView cited source
[14]
"The notion is so beautiful," said Pu Gao.
ReportedSupportedView cited source
[15]
"What attracts me most is actually the beauty of it," said Pu Gao.
ReportedSupportedView cited source
[16]
Pu Gao is a mathematician at the University of Waterloo in Canada who has worked on the sandwich conjecture.
ReportedSupportedView cited source
[17]
In the late 1950s Edgar Gilbert, studying telephone networks at Bell Labs, devised a simple model of a random graph in which vertices connect at random; Paul Erdos and Alfred Renyi independently came up with a similar model at around the same time.
ReportedSupportedView cited source
[18]
Regular graphs are random graphs in which all vertices have the same number of edges; they provide a better understanding of random structure than binomial graphs and are often much more accurate at modeling real-world networks.
ReportedSupportedView cited source
[19]
If random regular graphs can be approximated with random binomial graphs, mathematicians can get many hard-to-prove properties of a regular graph from the matching binomial graph for free.
ReportedSupportedView cited source
[20]
Quanta's account states the conjecture in terms of the graph being large enough and does not specify a size threshold.
ReportedSupportedView cited source
[21]
Proving the sandwich would also demonstrate that two very different random processes mathematicians like to study are connected in a deeper and more elegant way than they had imagined.
ReportedSupportedView cited source
[22]
A random binomial graph is built by taking a pair of vertices, flipping a potentially biased coin, drawing an edge on heads, and repeating for every pair.
ReportedSupportedView cited source
[12]
Adding the extra 20 years of work to a binomial-graph answer known by the 1970s places the regular-graph Hamiltonian result in roughly the 1990s.
DerivedSupported1 source— sign in to open
[13]
Twenty-one years separate the 2004 conjecture from the 2025 proof.
DerivedSupported1 source— sign in to open

Sources

Publishers with included, body-backed reporting in this cluster.

quantamagazine.org
1 article · September 18, 2026
Mathematicians Build Long-Awaited Graph Sandwich

Ask Clarity

Have a question this piece left open? The answer comes from its reporting and claim ledger — nothing else.

Try

Clarity analysis

How the coverage leans and what the record actually supports. Read the methodology

Perspective Coverage

How much of the coverage speaks to builders, operators and investors. It measures emphasis, not whether the story is right.

Quanta gives the construction in enough detail to follow. One random process builds both graphs in tandem; on the bottom half the binomial graph's edges are a subset of the regular graph's, so any property that only becomes likelier as edges are added transfers upward, and the top half runs the same argument in reverse for properties preserved by removing edges. Quanta does not cite the paper or give the degree range where the guarantee kicks in. 'Large enough' is as precise as the condition gets here.

Reality

Evidence, adoption, hype gap, incentives and confidence, each read independently from the current record on the scale shown beneath it. How these are measured.

Evidence58

0100

One outlet, no paper cited

Everything here rests on a single Quanta piece, which is specific where it can be: Kim and Vu with their 2004 affiliations, Gilbert's Bell Labs work dated to the late 1950s, the containment argument spelled out in both directions, and two working mathematicians quoted by name. Quanta does not cite the proof itself. The 2025 date in the introduction and the 2023 date in the body are never reconciled, and the copy available to us breaks off while naming the three authors.

AdoptionInsufficient

Too early to measure

A proof has no install base. Quanta explains what the sandwich buys, that hard properties of a regular graph follow from the easier binomial one, and does not point to any work that has since used it; the partial results it describes are steps toward the theorem rather than applications of it.

Hype gap+12

−100 understated0 aligned+100 overstated

Restrained prose, unqualified payoff

Topics and entities

Follow any of these and your For You feed starts watching them — no settings page required.

Topics

science
New four-color theorem proof buys planar-graph insight with more computation
1 publisher
science
A match-head snail in Lake Alexandrina doubled its genome under a million years ago
1 publisher
science
A combination of explanations leads the dark matter answers in the largest physicist survey
1 publisher
product
Squeezing the electrolyte turned lithium dendrites sideways in SLAC's test cells
1 publisher

Random regular graphs can now inherit their properties from the easier random model

What happened

Why it matters

What to watch

Claim ledger

Sources

Topics and entities

Topics

Entities

Claim ledger

Topics and entities

Topics

Entities

Perspective Coverage

Reality

Sources

What happened

Why it matters

What to watch

Claim ledger

Sources

Let Clarity write the post for you.

Topics and entities

Topics

Entities

Related stories

Claim ledger

Let Clarity write the post for you.

Topics and entities

Topics

Entities

Perspective Coverage

Reality

Related stories

Sources