Meyniel’s conjecture

Imagine a chase on dots joined by links. The pursuers and the evader see everyone’s position; they take turns moving along a link or staying put. A pursuer catches the evader by reaching its dot. How many pursuers are enough, however the links are arranged?

On a four-dot path A–B–C–D, one pursuer starting at B can catch an evader anywhere. On a four-dot loop A–B–C–D–A, an evader can keep opposite a single pursuer; two pursuers starting at A and C catch it on their first turn. The conjecture asks whether one fixed multiple of the square root of the number of dots always suffices in a connected network.[1]

In a visible chase, must the number of pursuers needed grow no faster than one fixed multiple of the square root of the number of places, even for the most evasive connected layout? The four-vertex path needs one pursuer; adding the closing edge makes a cycle requiring two. These are finite teaching cases, not a general bound.

For a finite connected undirected graph G, let the cop number $c(G)$ be the minimum team with a winning strategy. Cops choose starts before the robber, then move first on alternating turns; moving to a neighbor or staying is legal, and capture is shared occupancy. Perfect information means both sides know all current positions. The conjecture is one absolute constant $C$ such that $c(G)\leq C\sqrt{|V(G)|}$ for every such G.[1]

The path and loop show how links change the required team, but they cover only two small networks. The June 2026 preprint proves results under expansion or random-hypergraph hypotheses; these do not supply a strategy for every connected graph. The missing guarantee must allow any arrangement of links and every legal evasive strategy.[1]

The universal quantifier includes graphs without the expansion or probabilistic hypotheses used in the cited June 2026 preprint. Its restricted hypergraph results do not transfer automatically to every ordinary graph. Small winning strategies verify individual cop numbers; they do not control the growth of those numbers over arbitrary graph sizes and structures.[1]

Both examples have four places, yet a loop offers an escape route that the path lacks. Counting places or measuring the shortest distance to the evader does not capture this strategic difference. Studying pursuit connects the arrangement of a network with the resources needed to control all possible routes through it.[1]

A shortest-path problem follows one destination through a fixed graph; pursuit must anticipate a destination that changes in response to each move. The cop number therefore links local adjacency with a global adversarial strategy. Expansion and random-graph methods probe particular ways that many routes can coexist, while the conjecture asks how much strategic freedom can remain without any such structural assumptions.[1]