AFTD Auto-Formalizing Theoretical Domains

cop_win_two_of_dominating_pair

theoremverified

A graph admitting a 2-vertex dominating set has a winning strategy for 2 cops.

Statement

theorem cop_win_two_of_dominating_pair {V : Type*} (G : SimpleGraph V) (u v : V)
    (hdom : ∀ w : V, w = u ∨ w = v ∨ G.Adj u w ∨ G.Adj v w) :
    HasCopWinStrategy G 2
Source
step towards op_292_cop_number_p7_claw_free
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • CopsCanWinFromCops 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…
  • 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…

The proof, explained

The two cops win by initially placing one cop at u and the other at v. Because {u, v} is a dominating set, any starting vertex R of the robber is either already occupied by one of the cops or adjacent to one of them. If the robber starts on a cop, capture is immediate; otherwise, the adjacent cop moves onto the robber's vertex on the first turn while the other cop stays in place, capturing the robber in one step.

  1. To show that two cops have a winning strategy, it suffices to place them initially at u and v and show they can win against any initial robber position R.

    We choose the initial cop configuration C₀ that places cop 0 at u and cop 1 at v. By the definition of `HasCopWinStrategy`, we must show that for any vertex R chosen by the robber, the cops can win from C₀.

    lines 5–7

      let C₀ : Fin 2 → V := fun i => if i = 0 then u else v
      use C₀
      intro R
  2. In the case where the robber starts at u, the cops win immediately.

    Since {u, v} dominates the graph, the robber's position R satisfies R = u, R = v, u ∼ R, or v ∼ R. In the first case R = u, cop 0 already occupies R, so the cops win immediately by `CopsCanWinFrom.capture`.

    lines 8–10

    uses CopsCanWinFrom.capture

      rcases hdom R with hu | hv | hadj_u | hadj_v
      · apply CopsCanWinFrom.capture
        exact ⟨0, hu.symm⟩
  3. In the case where the robber starts at v, the cops win immediately.

    If R = v, cop 1 already occupies the robber's position (C₀(1) = v = R), so `CopsCanWinFrom.capture` completes the win without any moves.

    lines 11–12

    uses CopsCanWinFrom.capture

      · apply CopsCanWinFrom.capture
        exact ⟨1, hv.symm⟩
  4. In the case where the robber is adjacent to u, cop 0 can move to R to capture the robber in one step.

    We define a next configuration C' where cop 0 moves to R and cop 1 stays at v. By `CopsCanWinFrom.step_capture`, this wins the game: cop 0 makes a legal move along the edge between u and R (given by the adjacency assumption `hadj_u`), cop 1 remains stationary at v, and cop 0 now occupies R.

    lines 13–19

    uses CopsCanWinFrom.step_capture

      · let C' : Fin 2 → V := fun i => if i = 0 then R else v
        apply CopsCanWinFrom.step_capture C₀ R C'
        · intro i
          fin_cases i
          · right; exact hadj_u
          · left; rfl
        · exact ⟨0, rfl⟩
  5. In the case where the robber is adjacent to v, cop 1 can move to R to capture the robber in one step.

    Symmetrically, we define C' where cop 0 remains at u and cop 1 moves to R. By `CopsCanWinFrom.step_capture`, cop 0 stays put, cop 1 moves along the edge between v and R (given by `hadj_v`), and cop 1 now captures the robber at R.

    lines 20–26

    uses CopsCanWinFrom.step_capture

      · let C' : Fin 2 → V := fun i => if i = 0 then u else R
        apply CopsCanWinFrom.step_capture C₀ R C'
        · intro i
          fin_cases i
          · left; rfl
          · right; exact hadj_v
        · exact ⟨1, rfl⟩
CopsCanWinFrom.capture
If at least one cop is already at the robber's location, the cops have won from that state.
CopsCanWinFrom.step_capture
If the cops can legally transition to a new configuration where some cop is at the robber's location, the cops win from the current configuration.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- A graph admitting a 2-vertex dominating set has a winning strategy for 2 cops. -/theorem cop_win_two_of_dominating_pair {V : Type*} (G : SimpleGraph V) (u v : V)    (hdom : ∀ w : V, w = u ∨ w = v ∨ G.Adj u w ∨ G.Adj v w) :    HasCopWinStrategy G 2 := by  let C₀ : Fin 2 → V := fun i => if i = 0 then u else v  use C₀  intro R  rcases hdom R with hu | hv | hadj_u | hadj_v  · apply CopsCanWinFrom.capture    exact ⟨0, hu.symm⟩  · apply CopsCanWinFrom.capture    exact ⟨1, hv.symm⟩  · let C' : Fin 2 → V := fun i => if i = 0 then R else v    apply CopsCanWinFrom.step_capture C₀ R C'    · intro i      fin_cases i      · right; exact hadj_u      · left; rfl    · exact ⟨0, rfl⟩  · let C' : Fin 2 → V := fun i => if i = 0 then u else R    apply CopsCanWinFrom.step_capture C₀ R C'    · intro i      fin_cases i      · left; rfl      · right; exact hadj_v    · exact ⟨1, rfl⟩
See it in the graphDiscuss this resultChallenge it