AFTD Auto-Formalizing Theoretical Domains

CopsCanWinFrom

inductive

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_cycle is 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
See it in the graphDiscuss this resultChallenge it