GPT-5.6 Pro has produced a counterexample to the Dinitz-Garg-Goemans conjecture, a graph-theory statement that had remained unresolved for nearly 30 years. According to the MarsBit article, which credits the WeChat account Quantum Position and author Mengyao, researcher Dmitry Rybin used four prompts totaling 58 English words across the full exchange. The final output included a schematic, a four-page proof certificate, an exact exhaustive-verification program, machine-readable counterexample data, and LaTeX source code.
The bottom line was stark: the Dinitz-Garg-Goemans conjecture is false.
The conjecture sits in the study of single-source unsplittable flow. In plain terms, it can be pictured as a delivery problem. A warehouse needs to send goods to several destinations. If splitting is allowed, one shipment can be divided across multiple routes. If splitting is forbidden, each shipment must travel along one complete route and cannot be broken apart.
That setup is not just abstract mathematics. Similar constraints appear in network traffic, logistics orders, traffic scheduling, and supply-chain allocation. A mathematical optimum may divide demand into arbitrarily small pieces, while a truckload or an order in practice cannot be split into 0.37 of a unit.
Once splitting is disallowed, the original optimal plan is no longer easy to reuse. Load that had been spread over several roads now has to move in whole blocks, and some edges can see a sudden increase in congestion. The problem, then, is how to convert a splittable solution into an unsplittable one without letting edge loads blow up too much.
The conjecture and its cost condition
In 1999, Yefim Dinitz, Naveen Garg, and Michel Goemans published a classic paper on single-source unsplittable flow, showing that congestion in such a conversion can be kept within a bounded range.
But congestion was only one side of the question. Cost mattered too. Goemans later proposed a stronger cost-aware version, which became known as the Dinitz-Garg-Goemans conjecture. It says that while preserving the overload bound, the total cost should also stay no higher than the original splittable-flow solution.
Put simply, if splitting demand lets a solution stay cheap and not too congested, then forcing every demand to take one full path should still leave a solution that is just as cheap and increases load by at most one demand unit in the relevant sense described by the conjecture.
This seemingly intuitive statement was never proved in general graphs. Later work established only partial results in special cases. For years, it stood in that unresolved state, neither fully proved nor refuted.
A seven-node, nine-edge construction
The reported counterexample strikes exactly at the two conditions the conjecture wants at the same time: keeping loads within the stated bound and keeping total cost no higher than in the splittable case.
The construction uses a small directed graph with seven nodes and nine directed edges. It has one common source and three destinations. The three demands are 15, 10, and 15. Each demand has two route choices. One route is expensive and costs 30 per order. The other costs 0, but it shares parts of the network with the others.
If splitting is allowed, the three demands can divide their flow between the costly and free routes, and the total cost comes out to 58.
Under the unsplittable rule, that changes. GPT-5.6 Pro’s reported conclusion is that the three free-route options are pairwise incompatible. Any two demands choosing their free routes at the same time force some shared edge to carry 25, 30, or 40 units of load, while the corresponding allowed upper bounds are only 24, 29, and 39.
Each time, the excess is exactly 1 unit.
That means at most one of the three demands can take a free route if the load condition is to be respected. The other two must use the costly routes. Since each costly route adds 30 in cost, any feasible solution that meets the load requirement has minimum cost 60.
The contradiction is immediate. Keep the load within the conjectured bound, and the cheapest cost is 60. Push the cost back down to the splittable benchmark of 58, and at least one edge exceeds capacity. The conjecture claims both conditions can hold together. This example says they cannot.
Why the verification is manageable
The report says the example is not especially hard to verify. Each of the three destinations has two path options, so there are only 2^3 = 8 possible combinations.
Listing all eight cases yields four combinations that satisfy the capacity constraints, with costs of 90, 60, 60, and 60. The other four are cheaper, but all of them violate edge-load limits.
Every case can be checked by exhaustive enumeration, and the article says there are no omitted hidden paths. If the graph satisfies the original conditions of the conjecture, then the 2-unit gap between 58 and 60 is enough to refute it.
Four prompts, several rounds of failure
One of the most discussed parts of the story is the dialogue itself. The public exchange, as described in the article, did not involve pages of prompt engineering or a long sequence of added formulas. Aside from attached files, Rybin’s instructions were short and plain. Across the entire process, he entered four prompts with a combined length of 58 English words.
GPT-5.6 Pro then began searching. It first set up a linear-programming-based verification method. After that, it explored multiple structures, including hypercubes, layered graphs, and merge-fork networks, screening thousands of small instances along the way.
The first round did not work. The model reported that it had not found a valid counterexample. It also warned that packaging the approximate constructions found so far as genuine counterexamples would lead to an incorrect mathematical conclusion.
Rybin did not answer with new formulas or a detailed route to the solution. He pushed the model to continue and find a complete, unconditional counterexample. The second round failed as well. He then asked it to form a clearer strategy from the structure of the problem before searching again.
By the third round, the model had narrowed the search to a routing structure with only 24 states, but it still did not have a complete example. Only after Rybin’s fourth prompt, which called for finishing with a complete, unconditional counterexample, did GPT-5.6 Pro return the seven-node, nine-edge graph.
Candidate counterexamples kept collapsing
The full dialogue also shows that the model spent hours going down blind alleys. Several times it found candidate counterexamples that looked convincing at first. Then, after fully enumerating routes, it discovered previously missed mixed paths inside the network.
Those mixed paths stitched together segments from different preset routes, creating new ways through the graph and slipping around the capacity restrictions the model had been trying to enforce. So examples that looked valid at one stage collapsed during complete verification.
GPT-5.6 Pro’s own summary on that point was blunt: checking only a few hundred preset routes is not enough. A valid counterexample must account for all possible unsplittable routes in the network.
The authorship question
On the surface, Rybin contributed just 58 English words. But in the account presented by the article, his crucial role was recognizing that the first three rounds were only partial progress and refusing to stop early.
Wharton professor Ethan Mollick, after seeing the exchange, raised a question about credit: should the author of this work be Rybin, who wrote the 58 words, or GPT-5.6 Pro, which carried out the multi-hour derivation?
Whatever answer follows on authorship, the published record points to one practical lesson from this case. The model’s final package was not merely a verbal claim. It came with a figure, a four-page proof certificate, an exact exhaustive-verification program, machine-readable data for the counterexample, and LaTeX source files.
The article also notes that over the past week, AI systems have been moving quickly in the search for mathematical counterexamples, from the Jacobian conjecture to the Dinitz-Garg-Goemans conjecture.
The report was published by MarsBit and attributes the original piece to the WeChat account Quantum Position, written by Mengyao.