cop_win_two_of_dominating_pair
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.
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₀.
let C₀ : Fin 2 → V := fun i => if i = 0 then u else v use C₀ intro R
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`.
uses
CopsCanWinFrom.capturercases hdom R with hu | hv | hadj_u | hadj_v · apply CopsCanWinFrom.capture exact ⟨0, hu.symm⟩
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.
uses
CopsCanWinFrom.capture· apply CopsCanWinFrom.capture exact ⟨1, hv.symm⟩
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.
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⟩
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩