AI produces a challenge to a long-standing graph theory claim
A 30-year-old conjecture in graph theory has reportedly fallen after an AI system generated a counterexample in a matter of hours. According to New Scientist, Dmitry Rybin, co-founder of AI start-up Autokernel, used ChatGPT 5.6 Pro to search for a structured counterexample to the Dinitz-Garg-Goemans conjecture, a result that had stood as an open question in combinatorics and optimization for decades.
The report says Rybin used four prompts in total, amounting to fewer than 60 words, and that the model spent about 5.5 hours searching before returning a construction that shows the conjecture is false. If the counterexample holds up under expert scrutiny, the episode would mark another notable moment in a fast-moving pattern: AI systems are not only assisting with routine proof work or symbolic manipulation, but increasingly surfacing novel objects that change the status of established mathematical questions.
That shift matters because counterexamples occupy a special place in mathematics. A theorem can survive years of checking across many special cases, but a single valid exception is enough to collapse the general claim. In fields where intuition is built from patterns in smaller examples, finding the first object that breaks a rule can be unexpectedly difficult. It is exactly the kind of search problem where large-scale automated exploration may have an advantage.
What the conjecture was trying to say
The Dinitz-Garg-Goemans conjecture belongs to graph theory, the study of networks built from vertices and edges. New Scientist describes the claim through a logistics analogy. Imagine shipments leaving a warehouse for several destinations. In one version of the problem, the shipments can be split into smaller pieces and routed independently. The conjecture proposed that this flexible setup could be converted into another arrangement where shipments remain unsplittable, without increasing the total cost.
That kind of statement is attractive because it suggests messy real-world optimization can sometimes be reduced to cleaner, easier-to-analyze forms. If true, the conjecture would have implied a dependable bridge between split and unsplit flow scenarios. Instead, the reported counterexample indicates that the bridge does not always exist. Somewhere in the structure of these networks, there are cases where forbidding splitting does change the economics in a way the conjecture said it would not.
For specialists, that does not mean the whole area collapses. It means the frontier sharpens. Researchers can now ask where the conjecture fails, whether restricted versions still survive, and which classes of graphs preserve the desired behavior. A false conjecture often creates as much productive work as a true one, because it forces the field to replace a broad but inaccurate principle with a more precise map.
Why this case is drawing attention
Part of the reaction comes from the apparent simplicity of the prompting. Rybin told X, as quoted by New Scientist, that he had spent many weeks thinking about the problem himself. Yet the prompts described in the article were minimal: an initial instruction to find a breakthrough counterexample, followed by repeated requests to continue searching. That contrast has become central to the story. The interest is not only that an AI was involved, but that the human-facing interface looked so ordinary while the underlying computational search may have been doing something nontrivial.
That distinction is important. A short prompt does not mean the reasoning process was simple. It means the user did not need to handcraft a dense formal workflow to steer the system toward useful search. As AI tools improve, the bottleneck may move away from specifying every step and toward framing the right mathematical target, checking the output rigorously, and translating machine-generated objects into forms that a research community can verify and build on.
New Scientist also notes that this is the second time in a week that AI has been credited with overturning a long-standing conjecture. The article places the new graph theory result alongside an earlier AI-generated counterexample to the Jacobian conjecture and points back to an OpenAI model that reportedly cracked a decades-old conjecture by Paul Erdos in May. Taken together, these episodes suggest the current moment is not a one-off curiosity but part of a broader acceleration in machine-assisted mathematics.
Why graph theory may be especially vulnerable to surprises
Chris Bowman-Scargill of the University of York told New Scientist there is a running joke in mathematics that every conjecture in graph theory is false. The humor reflects a real structural challenge. In graph theory, behavior that looks stable in small examples can change abruptly when just one or two vertices are added. That makes informal pattern recognition less reliable than it may be in areas where low-rank examples tend to mirror larger structures more faithfully.
In that environment, automated systems are naturally useful. They can push beyond the range that humans casually inspect, enumerate cases at scale, and search for odd constructions that do not look intuitive at first glance. A mathematician may have a good conceptual feel for why a statement should be true, while a machine can relentlessly test whether that intuition survives in stranger corners of the space.
The likely lesson is not that mathematicians become obsolete. Instead, their role changes. Humans still decide which questions matter, evaluate the significance of a construction, identify the structural reason it works, and turn a raw computational output into a robust mathematical narrative. But the search landscape is changing. When machines can surface decisive examples faster and more often, conjecture-making itself may become more disciplined and more adversarial, with researchers expecting aggressive machine checking earlier in the life of an idea.
What comes next
The immediate question is verification. A claimed counterexample only changes the mathematical record after experts confirm that the object really does violate the conjecture under the exact formal conditions. New Scientist presents the result as a major development, but the long-term importance will depend on how the community validates, interprets, and extends it.
If the result stands, it will reinforce a trend that many researchers are already struggling to absorb. AI is moving from assistant to collaborator in discovery-oriented work, especially in domains where the search space is large but the success condition is crisp. Mathematics is a particularly visible test case because the outputs can, in principle, be checked with precision. That makes it easier to separate hype from substance than in many other intellectual fields.
Even so, the social effect may be larger than the single conjecture. A generation of mathematicians is now confronting the possibility that valuable insight may emerge from systems prompted in plain language, running for hours, and returning objects that humans did not think to construct. Whether that produces unease, excitement, or both, it marks a meaningful shift in how discovery may happen.
This article is based on reporting by New Scientist. Read the original article.
Originally published on newscientist.com