GPT-5.6 and the Dinitz-Garg-Goemans Conjecture

On July 22, 2026, Dmitry Rybin posted a claim on X that made a certain kind of person put down their coffee: GPT-5.6 Pro had produced a counterexample to the Dinitz-Garg-Goemans conjecture, open in combinatorial optimization for about 30 years. The proof of concept was one small graph. Fractional flow cost 58, unsplittable flow cost 60. Two points, three decades, four prompts.

Most coverage repeats the numbers without showing the mechanism behind them, and the mechanism is where the real lesson lives. It's also where I have to be straight with you about what has been verified and what hasn't. Short version: the concepts are solid, the news is a claim and not yet a theorem, and if you sit down to reproduce the exact graph from scratch, you learn why problems like this are hard the moment your reconstruction springs a leak.

The Quick Answer

Rybin reports that GPT-5.6 Pro, steered by four prompts totaling under 60 words, produced a claimed counterexample to Goemans' cost conjecture, a problem open since roughly 1999. His instance is a small directed graph with a single source and three delivery terminals. He states the splittable (fractional) routing costs 58, while any unsplittable routing that keeps congestion within the allowed budget costs at least 60. That two-point gap, if it survives formal review, is enough to sink the conjecture.

It has not been through peer review. Rybin published the full ChatGPT conversation so anyone can read the construction, and several people have checked his arithmetic and found it consistent. Reproducible arithmetic and an accepted proof are different animals, though, and the distance between them is the whole story of this article.

What Is the Dinitz-Garg-Goemans Conjecture?

Before we can appreciate what fell, or might have, we need to understand what the conjecture actually says.

Picture a warehouse shipping orders to three towns over a road network. If you're allowed to split a shipment, you can send half an order down one road and half down another. That's fractional routing, and it's flexible; it usually finds a cheaper set of paths. But a lot of real freight can't be split. One order, one truck, one road, start to finish. That's unsplittable flow, and it's what a freight order, a network packet, or a shipping container actually has to do.

The question people have chewed on since 1999 is simple to state. If a cheap splittable routing exists, can you always find an unsplittable routing that's also cheap without overloading the roads too badly?

Yefim Dinitz, Naveen Garg, and Michel Goemans settled half of it. The other half is the part GPT-5.6 went after. To understand why that distinction matters enormously, we need to be precise about it.

The Theorem vs. the Conjecture

This is the distinction most write-ups blur, so I'll be precise about it once and then rely on it for the rest of the article.

Dinitz, Garg, and Goemans proved a congestion result: given a valid fractional flow, you can always convert it to an unsplittable one without overshooting any road's capacity by more than the single largest demand, call that number D. That theorem is not in question and never was.

What Goemans separately conjectured is the stronger, cost-aware version: that the same conversion could hold the total cost down at the same time it holds congestion down. Congestion and cost, both bounded, in one routing. The congestion-only theorem is safe. The cost-plus-congestion conjecture is the piece Rybin says fell. If you take away one sentence from this piece, make it that one. A lot of the excited coverage quietly swaps the two, and the difference between them is the whole mathematical gap that took 30 years to close.

What GPT-5.6 Actually Built

Rybin's instance is small enough to describe in a paragraph. A source, a few intermediate nodes forming a shared "spine," and three terminals, each carrying a demand. Every terminal has two ways home: an expensive direct path, or a free detour through the shared spine.

The tension is structural. The cheap detours compete for room on the spine, so if too many terminals try to route cheap at once, a spine road overflows. Push that far enough and only one terminal can take its cheap path in any valid unsplittable routing. The rest are forced onto their expensive direct paths, and the cost climbs. The fractional flow, free to split, spreads each demand across both paths and slips under every capacity at once. That's how you get a fractional cost below the cheapest legal unsplittable cost. Rybin's figures for his instance are 58 and 60.

I'll be honest about a limit here. I have not been able to reproduce Rybin's exact graph, the specific capacities and the pairwise conflicts, from a primary source. His transcript describes a particular point in a parameter family, and the widely-shared "seven-node" description is an abstraction of it, not a construction I've verified edge by edge. So I'm not going to stage a tidy derivation of 58 and pretend it's his. What I can do is hand you a self-contained instance that shows the same mechanism, small enough to check by brute force, so you can see with your own eyes what "fractional beats every legal unsplittable" looks like. 

Four Prompts, Several Hours

The prompt count is the least interesting thing about this story, though it's the part that went viral.

The chat log Rybin shared shows the model failing first, and failing accurately. The opening prompt asked it to find a structured counterexample. It worked for the better part of an hour and came back empty, stating outright that presenting what it had as a valid counterexample would be false.

Told to keep going, it ran again, and again reported nothing, describing how each promising construction kept sprouting a hidden extra routing option that destroyed the cost-congestion separation once every path was enumerated. A third prompt asking for a cleaner strategy bought a narrower framework and still no finished result.

That's not "four prompts, done." That's hours of a model hitting walls and telling the truth about them. The specific wall it kept hitting, an extra route appears and ruins the separation, is exactly what the final construction was built to prevent, by pinning each terminal to precisely two paths so the whole routing space is eight options you can enumerate by hand. Keep that failure mode in mind. You're about to run into it yourself.

The fourth prompt, reportedly something close to "had enough of your failure, please finish with a complete unconditional counterexample," is the one that produced the working construction, along with proof certificates, an enumeration program, and full LaTeX. The patience mattered. So did the earlier refusals; they were honest self-assessments.

Check It Yourself

Here's where DataCamp coverage can do something a news post can't: let you run the verification.

A quick caveat before the code. What follows is not Rybin's graph. It's a schematic instance I built to be honest, one where each terminal genuinely has exactly two routes, the arithmetic closes, and the gap is real. It shows you the shape of such a counterexample and the technique for checking one. It does not, on its own, disprove anything, and I'll explain why right after you run it.

The setup: three terminals, each shipping 10 units, so the largest demand D is 10. Each has an expensive direct path (cost 30) and a free cheap path. The cheap paths are arranged so every pair of them fights over its own private bottleneck road, road A is shared by terminals 1 and 2, road B by terminals 1 and 3, road C by terminals 2 and 3. In the fractional flow, each terminal sends 2/5 of its demand cheap and 3/5 expensive, which costs 30 x 3/5 x 3 = 54. Each road then carries 4 + 4 = 8 units fractionally, and the congestion budget is that load plus D, so 18.

Now watch what unsplittable routing does to that. Two terminals both going cheap dump 10 + 10 = 20 units on their shared road, over the budget of 18. So at most one terminal can route cheap; the other two pay 30 each. Minimum legal unsplittable cost: 60. Against a fractional 54. Eight routings exist, so we just check all of them:

from itertools import product
	
# Three terminals, demand 10 each -> largest demand D = 10.
# Each has a cheap path (cost 0) and an expensive direct path (cost 30).
# Cheap paths pairwise share a PRIVATE bottleneck road, so every pair conflicts:
#   road A shared by {t1, t2},  road B by {t1, t3},  road C by {t2, t3}
# NOTE: this is a schematic instance to illustrate the check, not Rybin's graph.

demands = [10, 10, 10]
d_max = max(demands)          # congestion slack allowed on each road
cheap_frac = [2/5, 2/5, 2/5]  # expensive fraction is 3/5 each -> fractional cost 54
direct_cost = 30              # cost of one terminal's expensive path

# Which bottleneck roads each terminal's cheap path uses
uses = [
    {"A": True,  "B": True,  "C": False},  # t1: A, B
    {"A": True,  "B": False, "C": True},   # t2: A, C
    {"A": False, "B": True,  "C": True},   # t3: B, C
]

# The fractional flow saturates each road, so its load is that road's capacity
cap = {"A": 0.0, "B": 0.0, "C": 0.0}
for i in range(3):
    for road in cap:
        if uses[i][road]:
            cap[road] += cheap_frac[i] * demands[i]   # 8 units on each road

# Congestion rule: an unsplittable flow may exceed capacity by at most D
threshold = {road: cap[road] + d_max for road in cap}  # 18 on each road

fractional_cost = sum(direct_cost * (1 - cheap_frac[i]) for i in range(3))  # 54

print(f"Capacities (fractional load): {cap}")
print(f"Congestion budget per road  : {threshold}")
print(f"Fractional flow cost        : {fractional_cost}\n")
print(f"{'Route (0=cheap,1=exp)':22} {'Cost':>4} {'A':>3} {'B':>3} {'C':>3}  Valid")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = cheap, 1 = expensive
    cost = sum(direct_cost * c for c in choices)
    load = {"A": 0, "B": 0, "C": 0}
    for i, expensive in enumerate(choices):
        if expensive == 0:                    # this terminal takes its cheap path
            for road in load:
                if uses[i][road]:
                    load[road] += demands[i]
    ok = all(load[road] <= threshold[road] for road in load)
    tag = "OK" if ok else "overload"
    print(f"{str(choices):22} {cost:>4} {load['A']:>3} {load['B']:>3} {load['C']:>3}  {tag}")
    if ok:
        valid_costs.append(cost)

print(f"\nMin valid unsplittable cost: {min(valid_costs)}")
print(f"Gap: {min(valid_costs) - fractional_cost} (counterexample if > 0)")

Run it and you get a fractional cost of 54, a minimum legal unsplittable cost of 60, and a gap of 6. The three overloaded rows are the three pairwise conflicts; the only routings that survive keep at most one terminal cheap.

So the conjecture is dead? Not quite, and this is the part I promised to explain. That eight-row enumeration only tells the truth if each terminal really has two routes and no more. Build this graph out of actual roads and nodes, and a fourth cheap route tends to appear out of the combinatorics. A terminal finds a third way home that's cheap and stays under budget, and the gap closes. That extra route is the exact failure the model reported on its first three tries. A clean, symmetric gadget that breaks a 30-year conjecture in eight lines of Python would be too good to be true, and it is. The code above proves that the check is sound and the target property is real. Whether a given graph actually has that property, with no leaks, is the hard part, and it's why Rybin's real instance is a tuned point in a parameter family rather than a tidy triangle.

What's Still Unresolved

No formal paper has appeared. Rybin shared the conversation and the construction; neither has been through the referee process that would let the mathematical community officially close the conjecture.

The exact published graph hasn't been independently rebuilt from a primary source that I can find. The numbers circulating come from his post and the shared transcript. Several researchers have checked his arithmetic and called it consistent, and one showed his instance sits inside an infinite three-parameter family on the same nodes, which would make the result richer than a single lucky coincidence. Encouraging, but that's informal community checking, not a referee report. Treat the 58-vs-60 as a well-supported claim, not a settled fact.

The 1999 congestion theorem is untouched by any of this.

Part of a Pattern

This story isn't a single data point. It's the third conjecture reported to fall to AI assistance in about three months, and the pattern is worth dwelling on.

On July 20, Claude Fable 5 reportedly helped mathematician Levent Alpöge find a counterexample to the Jacobian conjecture, an 87-year-old problem. Before that, in May, an OpenAI model was said to have disproved the 80-year-old Erdős unit-distance conjecture. The same week as this news, a Columbia PhD student used GPT-5.6 with a structured Codex workflow to resolve six open Erdős problems in five days. The through-line, as one researcher put it, is that these systems are better at disproving than proving. A counterexample is a single witness you can check; a proof has to cover every case. That asymmetry seems to decide which problems fall first.

The practical takeaway isn't "AI solves math." What we're watching is AI working as a patient, combinatorially exhaustive search partner: one that can enumerate parameter families, hold failure modes in working memory across attempts, and tell the truth when a construction doesn't close. That's a specific, useful capability. And if you want to understand where it's likely to strike next, the question to ask isn't which conjectures are oldest, but which ones can be broken by a single checkable witness.