Dinitz-Garg-Goemans conjecture is false. This graph theory problem...
Dmitry Rybin@DmitryRybin1
554 views
Jul 22, 2026
~1 min read
Advertisement
1
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…
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…
2
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.
I think almost all graph flows experts thought about this problem.
3
The conjecture was based on absolutely stunning result of Dinitz, Garg, and Goemans: any fractional flow can be routed to unsplittable flow by violating graph capacities by at most max(demand).
The chat with gpt pro here is an absolute meme
The chat with gpt pro here is an absolute meme