AN AI'S PROOF, REDRAWN FOR HUMANS

Draw some dots and join some of them with lines. Mathematicians call this a graph; the dots are vertices, the lines edges, and the number of lines touching a dot is its degree. A tree is a graph with no loops that holds together in one piece, like a branching twig; a tree with t dots always has t − 1 lines.

In the early 1960s, Paul Erdős and Vera T. Sós asked a simple question: how many lines force a graph to contain every tree of a given size? Their answer, the Erdős–Sós conjecture, is this:

If a graph has an average degree greater than t − 2, it contains every tree with t vertices.

The threshold is sharp. Take separate copies of a complete graph with t − 1 dots, every pair joined: each dot has exactly t − 2 neighbours, yet no piece is big enough to hold a tree of t dots. The difficulty is the word average. If every single dot had at least t − 1 neighbours, one could place a tree branch by branch with no trouble. But an average says nothing about any individual dot: some may have hundreds of neighbours, others almost none.

Sixty years of partial answers

According to the history recounted in the paper, the problem dates from 1962–1964 and became central to the branch of mathematics that studies how many edges force a given pattern. Special cases fell: stars, paths, double stars, trees with few branches. In the early 1990s, four mathematicians — Ajtai, Komlós, Simonovits and Szemerédi — announced a proof for very large trees, but recent papers note that no full manuscript was ever published. Further partial results arrived in 2021, 2024 and 2026. On 4 September 2026, Reed and Stein posted a proof for large, dense graphs, which they state was developed without AI.

Then came a report. In September 2026, Tom Adamczewski and Thomas Bloom, in a document called FrontierMath Erdős, attributed a proof of the full conjecture to a pre-release version of an AI model, GPT-6 Astra. The original counting argument is public, and an accompanying repository records the AI’s autonomous search for the proof and a formal verification in the Lean proof-checking language. The report’s authors also called on human experts to write fuller, traditional accounts.

Revealing a graph one dot at a time

Jay Cummings, of California State University, Sacramento, answers that call. His 27-page article keeps the AI’s central counting argument but changes how it is told:

1. Reveal the graph gradually. List the vertices in some order and uncover them one at a time, along with the edges between those already shown.
2. Ask for more. Instead of any copy of the tree, look for one whose chosen “root” sits on the very first vertex. Asking for more makes the proof easier.
3. Count the early neighbours. These are the neighbours of the first vertex that show up before such a copy appears. Add them up over every possible order.
4. Bound the total. By swapping vertices or whole blocks of the order — moves that can always be undone — Cummings shows that, on average over all orders, there are at most t − 2 early neighbours.

The final step is short. If the graph contained no copy of the tree, every neighbour of the first vertex would be early, in every order. Averaged over all orders, that is exactly the average degree — which by assumption exceeds t − 2. Contradiction: the tree must be there.

The proof uses only the total of the degrees, not how they are spread out. Cummings also gives a probabilistic version, and works through trees with four and five vertices on concrete graphs.

A picture-book of a proof

The article contains 32 figures. It closes with a classic consequence: colour all the lines of a complete graph with q colours, and one colour will always contain a given tree once the graph has q(t − 2) + 2 vertices. In a final statement, Cummings explains that he developed the text in a long dialogue with ChatGPT, that the new presentation ideas — early neighbours, the explicit partitions, the drawings — are his, and that he checked everything and takes full responsibility.

He compares his account with other recent ones by Riordan and Scott, Wood and Frederickson, and notes that the method has already been extended to networks with directions and to “hypergraphs”, some of those extensions also attributed to GPT-6 Astra. His contribution, he writes, is “a reader-centered, visual exposition of the argument, not a new resolution of the conjecture.”