Mathematicians have a running joke about graph theory. ChatGPT just proved them right.

Graph theory has a running joke: add one or two vertices and the conjecture dies. Last week, Dmitry Rybin spent 5.5 hours and four ChatGPT prompts, fewer than 60 words in total, letting GPT-5.6 Pro find the next victim, a counterexample to the 30-year-old Dinitz-Garg-Goemans conjecture about how costs flow through networks.

Rybin, co-founder of the AI start-up Autokernel, said he had previously spent weeks trying to prove or disprove the conjecture himself, and that nearly everyone working on graph flows had looked at it (New Scientist). His initial prompt told the model to find a structured counterexample; three follow-ups simply asked it to keep going (Rybin on X).

The result is a graph on which the cheapest fractional flow costs 58, but any unsplittable flow, the kind the conjecture required, costs at least 60 when capacity violations are bounded by 15. That gap is what disproves the claim. A second post by Rybin walks through the construction (Rybin on X), and a follow-up by another X user, @basedjensen, shows Rybin's example is one point in an infinite 3-parameter family of counterexamples on seven-node graphs, parameterised by integers b, m, g with m ≤ b−g and m(b−m) > (b+m)g. Rybin's specific graph corresponds to (b, m, g) = (10, 5, 1) scaled by one fifth (basedjensen on X).

The conjecture, sometimes called the unsplittable-flow conjecture, sits in a corner of graph theory (a branch of math about networks and connections) where brute-force search over a finite-but-vast space is plausible, but local patterns reliably fool humans. "It's a running joke within the graph-theory community that you can take an existing conjecture, add a single vertex, and have a counterexample," Chris Bowman-Scargill told New Scientist. That is why four prompts were enough.

The disproof is the latest in a 2026 cluster of AI-assisted counterexamples. In May, an OpenAI model cracked an Erdős conjecture. The same week, a separate group reported an AI-driven counterexample to the nearly century-old Jacobian conjecture. Users are also claiming AI solutions to a Graffiti conjecture and another graph-theory problem, and a community site has appeared to catalogue the pattern by model (VibeMathed). The right prior is on the cluster, not on any single case: when a problem is shaped like "find a small object that breaks a stated rule," an LLM with enough search budget is now a credible tool. When a problem is shaped like "prove that no such object can exist," the track record is much thinner. Abhishek Saha of Queen Mary University of London noted to New Scientist that current models appear particularly well-suited to problems of this class.

A caveat applies: the disproof has so far been documented through Rybin's own X posts and New Scientist's reporting. No independent peer-reviewed or arXiv write-up confirming the counterexample has been cited in the available artifacts, so the result is currently claimed-by-discoverer, not refereed. The conjecture statement and authorship, Dinitz, Garg, and Goemans, are consistent across the reporting, Rybin's posts, and the community problem page (VibeMathed).

The next test is whether anyone can re-derive Rybin's example from the published description, and whether the parametric family @basedjensen sketched holds up under independent checking. If it does, the Dinitz-Garg-Goemans conjecture joins a growing list of "the joke got there first" cases, the kind of math where, for now, the easiest counterexample is sometimes the one an LLM hands you.