Meyniel's Conjecture on Cop Number

Meyniel’s Cop-Number Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

In the standard visible cops-and-robber game on a finite connected graph, cops first choose vertices and the robber then chooses a vertex; the sides move alternately along an edge or stay in place. The cops win by sharing a vertex with the robber. Let $c(G)$ be the minimum number of cops guaranteeing capture. Seek an absolute $C$ such that $c(G)\leq C\sqrt{|V(G)|}$. [S1] [S2]

Statement recorded in the supplied source.

Is the cop number of a connected n-vertex graph $O(\sqrt{n})$? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove Meyniel's bound or find a counterexample. [S1]

Short English statement

Can a constant times the square root of the number of vertices always suffice for visible cops to catch a robber on a connected graph?

Research attempt

Status: UNRESOLVED. We prove capture on trees, a domination bound with explicit minimum-degree dependence, and a reduction through a guarded feedback vertex set. These give the desired square-root scale for restricted classes but do not control arbitrary connected graphs.

Context and strategy.

Baird--Bonato's survey [E1], checked 1 October 2026, supplies the standard visible-game formulation and context. The inherited host URL [S2] failed to load directly in this pass, so the primary arXiv record is listed separately. No best-current general cop-number bound is asserted. We try two elementary ways to prevent evasion: dominate all possible starting points, or block cycles and pursue inside a tree.

One cop captures on a finite tree.

Put a cop at any vertex. If the robber is elsewhere, move the cop one step along the unique path toward the robber. After the move, unless capture occurs, delete the cop's new vertex from the tree. The robber lies in a component strictly contained in the component on the robber's side of the previous cop position. The robber cannot leave that new component without passing through the occupied vertex. Thus after each cop move the possible containing component strictly loses at least one vertex. It cannot shrink indefinitely in a finite tree, so capture occurs.

Uniqueness of the path is essential: on a graph with a cycle, the robber can sometimes move around the guarded vertex. Merely selecting a spanning tree does not remove the other edges from the actual game. The tree proof therefore cannot be applied to an arbitrary graph by ignoring those edges.

Domination gives an immediate capture bound.

A dominating set $S$ has the property that every vertex is in $S$ or adjacent to a vertex of $S$. Place one cop at each point of $S$. A robber choosing an occupied vertex is captured immediately; otherwise an adjacent cop captures on the first cop move. Hence $c(G)\le\gamma(G)$.

Let the graph have order $n$ and minimum degree $\delta\ge1$. Select each vertex independently with probability $p$, obtaining $S_0$, and add every vertex not dominated by $S_0$. The enlarged set $S$ dominates. A fixed vertex fails domination only when its closed neighborhood is entirely unselected, an event of probability at most $(1-p)^{\delta+1}\le e^{-p(\delta+1)}$. Consequently \[ \mathbb E|S|\le np+ne^{-p(\delta+1)}. \] Choose $p=\log(\delta+1)/(\delta+1)$, which lies in $[0,1]$. Some outcome satisfies \[ c(G)\le\gamma(G)\le \frac{n(1+\log(\delta+1))}{\delta+1}. \] The expectation argument is an existence proof and uses independence only to evaluate the probability of missing a single closed neighborhood. A deterministic search over all subsets would locate such a set but is not claimed efficient.

If $\delta+1\ge\sqrt n(1+\log n)$, the displayed expression is at most $\sqrt n$. This proves the requested scale in that high-minimum-degree regime. When minimum degree is bounded, however, the same expression is proportional to $n$ and does not imply Meyniel's bound.

A feedback-set reduction.

Suppose deleting a vertex set $S$ leaves a forest. Station one cop at every vertex of $S$ and keep those cops fixed. The robber must stay in one component of $G-S$, because moving through $S$ is capture. One extra cop can travel through the connected graph to that component. Upon entry, the one-cop tree strategy captures the robber; the extra edges from the component to $S$ do not offer an escape. Hence \[ c(G)\le |S|+1. \] This proves an $O(\sqrt n)$ bound for graphs having a feedback vertex set of that order. Empty $S$ gives the tree case, while the bound is only an upper estimate and need not equal the actual cop number.

Why these two reductions do not combine automatically.

Low minimum degree does not imply a small feedback vertex set. Conversely a high-degree core may be connected to many low-degree appendages, so a minimum-degree estimate on the entire graph can miss its structure. A proposed induction deleting a low-degree vertex would have to show how a winning strategy on the remaining graph handles visits to that vertex without spending a fresh cop at every deletion. Reserving one cop per deleted vertex can accumulate linear cost.

There is no monotonicity assertion here that adding edges can only help the cops. Added edges help the robber move as well. Every reduction was justified in the original game: domination by direct capture and feedback deletion by actually occupying the deleted set.

Verification and remaining gap.

For a single-vertex graph, one cop suffices separately; the random-set calculation assumes $\delta\ge1$. On a complete graph a single dominating vertex gives the exact answer, although the probabilistic bound is weaker. Staying in place is allowed throughout and never invalidates the shrinking-component invariant. No finite game search is claimed for this file.

The unresolved step is a strategy using at most $C\sqrt n$ cops without either a high minimum degree or a small cycle-blocking set. A useful next target is an induction that reuses guards while deleting low-degree regions, with a proved bound on their simultaneous number. The present argument supplies explicit special-class strategies but does not establish that invariant.

Sources

• E1 W. Baird and A. Bonato, Meyniel's conjecture on the cop number: a survey. Primary arXiv record checked 1 October 2026. https://arxiv.org/abs/1308.3385.

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1391 (GRAPH-004), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Meyniel's conjecture survey. https://math.ryerson.ca/~abonato/papers/meyniel_0311.pdf. Bibliographic information from the supplied record.