CopsCanWinFrom
Cops can force capture from cop positions C and robber position R in the cops and robber game with c cops on G if the robber is already captured, can be captured in the next cop turn, or for some legal cop move, cops can win from every legal subsequent robber response.
Statement
inductive CopsCanWinFrom {V : Type*} (G : SimpleGraph V) (c : ℕ) : (Fin c → V) → V → Prop
- Defined in
- arXiv:2610.20129 Sec. 1
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 3
- cop_win_two_of_dominating_pairA graph admitting a 2-vertex dominating set has a winning strategy for 2 cops.
- not_cop_win_two_of_dominating_cycleThe statement
cop_win_two_of_dominating_cycleis false: The theorem is FALSE. A concrete counterexample is the Petersen graph P on 10… - HasCopWinStrategyThe cop player has a winning strategy with c cops on G if there exists an initial placement of cops from which the cops can capture the…
Read back from the Lean
CopsCanWinFrom is an inductive predicate parameterized by a type V, a simple graph G on V, and a natural number c (representing the number of cops), with arguments C : Fin c → V (the positions of the cops) and R : V (the position of the robber), asserting that the cops can force a win from position (C, R).
It is defined with three constructors:
1. capture: If there exists i : Fin c such that C i = R (a cop already occupies the robber's vertex), then CopsCanWinFrom G c C R.
2. step_capture: If there exists a new cop configuration C' : Fin c → V such that every cop i : Fin c either stays put (C' i = C i) or moves to an adjacent vertex (G.Adj (C i) (C' i)), and at least one cop lands on the robber's current position (∃ i, C' i = R), then CopsCanWinFrom G c C R.
3. step: If there exists a new cop configuration C' : Fin c → V such that every cop i : Fin c either stays put (C' i = C i) or moves to an adjacent vertex (G.Adj (C i) (C' i)), and for every vertex R' : V, whenever the robber stays put (R' = R) or moves to an adjacent vertex (G.Adj R R'), the resulting position satisfies CopsCanWinFrom G c C' R', then CopsCanWinFrom G c C R.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Inductive predicate asserting that cops can force capture of the robber from a given position. -/ inductive CopsCanWinFrom {V : Type*} (G : SimpleGraph V) (c : ℕ) : (Fin c → V) → V → Prop where | capture (C : Fin c → V) (R : V) (h : ∃ i, C i = R) : CopsCanWinFrom G c C R | step_capture (C : Fin c → V) (R : V) (C' : Fin c → V) (hC : ∀ i, C' i = C i ∨ G.Adj (C i) (C' i)) (hcap : ∃ i, C' i = R) : CopsCanWinFrom G c C R | step (C : Fin c → V) (R : V) (C' : Fin c → V) (hC : ∀ i, C' i = C i ∨ G.Adj (C i) (C' i)) (hR : ∀ R', (R' = R ∨ G.Adj R R') → CopsCanWinFrom G c C' R') : CopsCanWinFrom G c C R