Cop number¶

The minimum number of pursuers required to guarantee capture of an evader in the standard cops-and-robber game on a graph.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3908
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics

Core Idea¶

The value depends on turn order, visibility, movement, capture and graph conventions; directed, fast-robber and invisible variants define different parameters. Cops choose initial vertices, the robber responds, players alternate along edges or wait and the least team size having a winning strategy over every robber response is assigned to the graph. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

How Many Cops to Catch?

Draw dots joined by roads. Some cops and one robber stand on dots and take turns moving along a road or staying still. The cop number is the smallest number of cops that can always catch the robber, no matter how cleverly the robber runs.

Fewest Cops That Always Win

The cop number is a puzzle number for a map made of dots and lines, which mathematicians call a graph. First the cops pick dots to stand on, then the robber picks a dot. Then they take turns: each one can move along a line to a next-door dot or stay put. The cops win if one lands on the robber. The cop number is the fewest cops needed to have a plan that always wins, whatever the robber does. Changing the rules — like letting the robber run faster or be invisible — gives a different number.

Minimum Pursuers to Guarantee Capture

The cop number of a graph is the minimum number of cops that have a guaranteed winning strategy in the game of cops and robber played on it. The cops place themselves on vertices first, the robber then chooses a vertex, and they alternate turns, each moving along an edge or waiting; the cops win by occupying the robber's vertex. 'Guaranteed' means the strategy works against every possible robber response, not just a careless one. The number depends on the exact rules: who moves first, whether everyone can see everyone, how far pieces move, what counts as capture, and what kind of graph is allowed. Variants such as directed graphs, a fast robber, or an invisible robber define different parameters, not the same one measured differently.

The cop number c(G) is a graph invariant defined via a pursuit–evasion game: it is the least k such that k cops have a winning strategy against every robber strategy on G. Under the standard conventions, cops choose initial vertices, the robber then chooses a vertex with full information, and players alternate moves along edges or remain in place, with capture occurring when a cop occupies the robber's vertex. The quantifier structure — there exists a cop strategy such that for all robber responses capture occurs — is essential, and the minimization over team size is what makes it a number attached to the graph. Its value is sensitive to every convention: graph class and finiteness, initial placement order, turn order, whether waiting is allowed, information available, movement speed, and the capture condition. Directed-graph, fast-robber, and invisible-robber versions are distinct parameters, so a claim about 'the cop number' must state which game it refers to.

Scope of Application¶

Cop number belongs to graph theory and is useful where the analyst can specify the typed graph theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, then evaluate the graph class and finiteness, number and placement of cops, robber placement, turn order, legal moves and waiting, information and capture condition, winning strategy quantifiers and minimized cop count are explicit. The scope is broad within that domain but bounded by the need for the graph class and finiteness, number and placement of cops, robber placement, turn order, legal moves and waiting, information and capture condition, winning strategy quantifiers and minimized cop count are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the graph class and finiteness, number and placement of cops, robber placement, turn order, legal moves and waiting, information and capture condition, winning strategy quantifiers and minimized cop count are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Cop number. Cop number compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed graph theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the graph class and finiteness, number and placement of cops, robber placement, turn order, legal moves and waiting, information and capture condition, winning strategy quantifiers and minimized cop count are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of graph theory because they reuse the typed graph theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, Cops choose initial vertices, the robber responds, players alternate along edges or wait and the least team size having a winning strategy over every robber response is assigned to the graph., and type the carrier, state every parameter and convention in the definition, test that the graph class and finiteness, number and placement of cops, robber placement, turn order, legal moves and waiting, information and capture condition, winning strategy quantifiers and minimized cop count are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Cop number Domain-specific

Parents (1) — outgoing typed relations

Cop number is a kind of Game-Theoretic Strategy Prime

It remains its own entry because its identity is fixed by the graph class and finiteness, number and placement of cops, robber placement, turn order, legal moves and waiting, information and capture condition, winning strategy quantifiers and minimized cop count.

Hierarchy path (1) — routes to 1 parentless root

Cop number → is a kind of Game-Theoretic Strategy → is a decomposition of Function (Mapping)

Neighborhood in Abstraction Space¶

Cop number sits in a crowded region of the domain-specific corpus (3^rd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Pursuit Games on Graphs (5 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25