Facial Distance Patterns in Planar Graphs
For a designated face of an undirected unweighted planar graph, how many distinct distance patterns can vertices have? Li and Parter (STOC 2019) proved an upper bound; Mozes, Wallheimer and Weimann conjectured the true answer matches their lower bound. Proved, closing the gap.
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Planar graph algorithms
- Posed by
- Shay Mozes, Benjamin Wallheimer, Oren Weimann (ISAAC 2022)
- Year posed
- 2022
- Years open
- 4y
- Solved
- 2026-08-07
- Model
- GPT-5.6 Sol
- Vendor
- OpenAI
- Collaborators
- Viktor Fredslund-Hansen, Shay Mozes, Oren Weimann
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Three immediate consequences follow for undirected unweighted planar graphs: better compression of the Okamura-Seymour metric, less space for constant-time exact distance oracles, and a faster distributed algorithm.
What the AI did
"The simple proof was found by OpenAI's GPT 5.6-Sol model", and the paper says it came from a single prompt describing the state of the art and asking for any improvement on the upper bound. The authors are candid about what that means: "It is surprising (not to say embarrasing) that this open problem has such a simple proof, which has eluded the community despite the human efforts invested in it." Section 2 of the paper is titled The ChatGPT Proof.
Verification
A preprint days old with no independent review. The argument is short and self-contained, turning on the observation that a pattern's entries must sum to plus or minus one because the face is a cycle.