Imagine trying to hide a tree inside a network. The tree might be a simple chain, a star with many spokes, or a more tangled branching shape. The network can have far more connections overall than the tree needs, yet some of its vertices may be nearly isolated. Can the network’s average number of neighbors still force every possible tree of a given size to appear?
That question resisted a complete answer for more than six decades. In 1963, Paul Erdős and Vera Sós conjectured a precise threshold: if a graph’s average degree exceeds the number of vertices in a chosen tree minus two, then the graph contains a copy of that tree. The challenge is hidden in the word average. Averages reveal the total, not where the connections are concentrated.
Consider a target tree with eight vertices. The conjecture says that an average degree greater than six guarantees a copy of every such tree, no matter how the network’s connections are distributed. The cutoff is exact: a collection of separate seven-vertex complete graphs has average degree six, but none can hold a connected tree with eight vertices. One extra bit of average density, it seemed, had to tip the balance—but how could it do so without ensuring that every individual vertex had enough neighbors?
A greedy search offers a tempting dead end. To build a tree one vertex at a time, you might demand that every network vertex have at least as many neighbors as the tree has vertices, minus one. Then each new branch has somewhere to go. But an average-degree condition does not guarantee that minimum degree. A graph can have very well-connected hubs and many poorly connected vertices. The usual step-by-step construction can stall.
The proof takes a less direct route. Instead of choosing a promising place to start, put every vertex of the network into a uniformly random order. Fix a rooted version of the target tree and examine edges from the first vertex in the order. An edge earns a special status if the part of the tree needed to complete it can already be found among vertices that appear earlier than the edge’s other endpoint.
Call such an edge a jumping edge. The name describes its role: as the ordering advances, the edge jumps past a ready-made partial tree, allowing that partial tree to be completed into a larger one. The key question is no longer whether a particular starting point works. It is whether, averaged over all possible vertex orders, enough edges must become jumping edges.
Here is the proof’s surprising accounting rule: for a rooted tree with a certain number of vertices, the expected number of its jumping edges is at least the graph’s average degree minus that tree size, plus one. That statement is proved by induction, building up from smaller rooted trees. But induction alone does not explain why edges that could support a partial tree should line up with edges that complete the larger one. The proof needs a way to compare different orderings.
When the root has just one branch, the comparison comes from swapping the positions of two vertices. A candidate edge that can support the smaller tree in one ordering corresponds, under the swap, to an edge that completes the larger tree in another. In any fixed ordering, at most one useful candidate escapes this pairing. So growing the tree by one vertex costs at most one expected jumping edge.
When the root branches, the bookkeeping gets subtler. The tree is split into two smaller rooted pieces. The proof counts edges that can support one piece on one side of the ordering and the other piece on the opposite side. Then it reverses a carefully chosen stretch of the ordering. This reversible rearrangement preserves the uniform distribution of orders while bringing the two pieces together on the same side of an edge. What looked like two separate partial matches can now complete the full tree.
Those swaps and reversals are the answer to the original puzzle: they turn local possibilities into a global count. Now remove a leaf from the target tree, leaving a smaller rooted tree behind. If the graph does not contain the original tree, there can be no jumping edge for this smaller tree—because any one would let you attach the missing leaf. Yet the counting rule says the expected number of these edges must be positive whenever the graph’s average degree exceeds the target size minus two. Zero and positive cannot both be true. The graph must contain the tree.
The argument also explains why a weak-looking average can be so powerful. It does not find one universally good starting vertex. Instead, it measures opportunities across every ordering, then uses reversible pairings to show those opportunities cannot all disappear. The network may hide its structure in any one snapshot; it cannot hide it across the entire space of possible orderings.
In September 2026, Oliver Riordan and Alex Scott posted a short arXiv exposition of this proof, which they report was discovered by GPT-6 Astra. Their paper also extends the method to certain directed trees and identifies graphs that sit exactly at the threshold without containing the target tree. The striking point is not simply that a long-standing problem got an answer. It is that the answer turns on a small, almost playful maneuver—reordering vertices—used to make a global promise emerge from an uneven network.
