---
id: "2026-07-22-dinitz-garg-goemans-conjecture-disproved-gpt-5-6-pro"
url: "https://postcutoff.com/e/2026-07-22-dinitz-garg-goemans-conjecture-disproved-gpt-5-6-pro/"
as_of: "2026-10-19T22:14:00+02:00"
date: "2026-07-22"
date_precision: day
category: science
importance: 3
confidence: medium
status: [Awaiting review]
verification: Expert-checked
sources: 4
editor: human editor
human_review: null
version: null
---

As of: 2026-10-19 22:14 CEST.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-07-22-dinitz-garg-goemans-conjecture-disproved-gpt-5-6-pro/

# Dmitry Rybin posts a GPT-5.6 Pro counterexample to the ~30-year-old Dinitz–Garg–Goemans (Goemans cost) conjecture on unsplittable flows

On 22 July 2026 Dmitry Rybin posted on X that the Dinitz–Garg–Goemans conjecture, open for about 30 years, is false, with a small graph found in a chat with GPT-5.6 Pro: a fractional flow of cost 58 for which every unsplittable flow with capacity violation at most 15 costs at least 60. He shared the full chat. The post had ~4.9M views. No paper or peer review has followed as far as we found.

## Key facts
- Rybin on X (22 July 2026, ~4.88M views by Oct 19, fxtwitter): '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.' The post links the ChatGPT conversation with GPT-5.6 Pro
- What is refuted (DataCamp): the cost version, Goemans' conjecture that a cheap splittable flow can be turned into an unsplittable one keeping both congestion and cost bounded; the Dinitz–Garg–Goemans congestion theorem itself is not in question
- Construction (as reported by 36Kr and DataCamp): one source, three terminals with demands 15, 10 and 15; fractional cost 58 vs ≥ 60 for any unsplittable routing within the congestion budget. DataCamp could not reproduce the exact graph from a primary source
- Checks: DataCamp says several people checked the arithmetic and found it consistent and one researcher placed the instance in an infinite three-parameter family; QbitAI/36Kr says the deliverables included proof certificates, an exhaustive enumeration program and LaTeX source. No named expert statement found
- Seen by us only on 19 Oct 2026, through Fireship's video 'Summer math fell to the machines' (Aug 19); Chinese tech press (36Kr, 24 July) covered it the same week together with Shouqiao Wang's six Erdős problems

## What happened

Rybin asked GPT-5.6 Pro for a complete counterexample to the conjecture and posted the resulting graph and the conversation. The claim spread
widely on X (one of the most viewed AI-maths posts of the summer) and in Chinese tech media. We read the X post (via fxtwitter), DataCamp and
36Kr; the open-since year is DataCamp's "roughly 1999", which fits Rybin's "~30 years". The construction details are secondary; verify against
the chat before relying on them.

## Why it matters

It is one of several AI-found counterexamples posted in July 2026 (see the Jacobian, Hessian and Rota-flats entries of the same week) and was
missed by this dataset for three months because it lived only on X and in a chat log, with no arXiv paper.

## What is disputed or not yet verified

- Verification: Unverified claim (X post with chat log); arithmetic reportedly checked by others; no paper or peer review found

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 83 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 22 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 113 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 52 days after its cutoff

## Sources

1. [DataCamp: GPT-5.6 and the Dinitz-Garg-Goemans conjecture](https://www.datacamp.com/blog/gpt-5-6-dinitz-garg-goemans-conjecture) (datacamp.com, press)
2. [36Kr: GPT-5.6 disproves 30-year graph theory conjecture; Peking University alumnus solves six Erdős problems in five days (24 July)](https://eu.36kr.com/en/p/3908956256605577) (eu.36kr.com, press)
3. [Dmitry Rybin on X: Dinitz-Garg-Goemans conjecture is false (22 July 2026)](https://x.com/DmitryRybin1/status/2079904005652893709) (x.com, discussion)
4. [ChatGPT conversation with GPT-5.6 Pro (shared by Rybin)](https://chatgpt.com/share/6a60b2eb-0b64-83ee-9c76-7931ca1de063) (chatgpt.com, discussion)

## Changes

- 2026-10-19 (filed): Created. Late from the 2026-10-19 lead (Fireship video); X post read via fxtwitter

## Related

- 2026-07-25: [Sharp thin-shell inequality](https://postcutoff.com/e/2026-07-25-sharp-thin-shell-inequality-gpt-5-6-pro/index.md)
- 2026-07-24: [Hessian conjecture refuted in five variables, derived from Claude-found Jacobian counterexample](https://postcutoff.com/e/2026-07-24-hessian-conjecture-counterexample/index.md)
- 2026-07-22: [Columbia PhD student Shouqiao Wang says he solved six open Erdős problems in five days with GPT-5.6 Sol in Codex, and publishes his workflow](https://postcutoff.com/e/2026-07-22-shouqiao-wang-six-erdos-problems-gpt-5-6-sol-codex/index.md)
- 2026-07-20: [Claude Fable 5 finds a counterexample to the Jacobian conjecture in dimension 3](https://postcutoff.com/e/2026-07-20-jacobian-conjecture-counterexample/index.md)
- Archived: 1 post, listed in https://postcutoff.com/e/2026-07-22-dinitz-garg-goemans-conjecture-disproved-gpt-5-6-pro/index.json