# GPT 5.6 Pro finds counterexample to Dinitz-Garg-Goemans conjecture

> Source: <https://xcancel.com/DmitryRybin1/status/2079904005652893709>
> Published: 2026-07-23 04:01:53+00:00

Dinitz-Garg-Goemans conjecture is false. This graph theory problem was open for ~30 years.
The graph below has fractional flow cost 58. Any unsplittable flow (with capacity violation <=15) has cost at least 60.
Chat with GPT 5.6 Pro where this was found:

[chatgpt.com/share/6a60b2eb-0…](https://chatgpt.com/share/6a60b2eb-0b64-83ee-9c76-7931ca1de063)Jul 22, 2026 · 12:18 PM UTC

186

662

7,566

2,566,273

I know counterexamples to old conjectures are becoming a meme at this point. But I really cared about this problem and spent many weeks thinking about it a while ago (in both directions, proof and disproof).
I think almost all graph flows experts thought about this problem.

12

11

1,536

107,200