not_cop_win_two_of_dominating_cycle
The statement cop_win_two_of_dominating_cycle is false: The theorem is FALSE. A concrete counterexample is the Petersen graph P on 10 vertices:
1. P contains an induced 5-cycle C = (v₀, v₁, v₂, v₃, v₄) with m = 5 ≥ 3.
2. C dominates P: the outer vertices are on C, and every inner vertex u_i is adjacent to v_i ∈ C.
3. However, the cop number of the Petersen graph is 3 (Aigner and Fromme, 1984, Theorem 3: the Petersen graph is the unique smallest graph with cop number 3). Thus 2 cops do not have a winning strategy on P: ¬ HasCopWinStrategy P 2.
The statement in attempt #5490 was adapted from Gupta–Pradhan–Swain (arXiv:2610.20129) where the graphs were assumed to be claw-free. The author omitted IsClawFree G (and hole length restrictions), believing any dominating cycle allows 2 cops to win. But the Petersen graph has claws (e.g. {v₀, v₁, v₄, u₀} is an induced claw K_{1,3}), which allows the robber to evade 2 cops indefinitely.
Statement
theorem not_cop_win_two_of_dominating_cycle : ¬ (∀ {V : Type*} [Fintype V] (G : SimpleGraph V) (m : ℕ) (hm : 3 ≤ m) (f : SimpleGraph.cycleGraph m ↪g G) (hdom : simple_graph_is_dominating G (Set.range f)), HasCopWinStrategy G 2)
- Related work
- refutes `cop_win_two_of_dominating_cycle`
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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…
- simple_graph_is_dominatingA subset S of vertices in a simple graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Lean source view module on GitHub
set_option maxHeartbeats 4000000 /-- Adjacency of the Petersen graph on `Fin 5 × Bool`. -/ def not_cop_win_two_of_dominating_cycle_petersen_adj (a b : Fin 5 × Bool) : Prop := (a.2 = false ∧ b.2 = false ∧ (b.1 = a.1 + 1 ∨ a.1 = b.1 + 1)) ∨ (a.2 = true ∧ b.2 = true ∧ (b.1 = a.1 + 2 ∨ a.1 = b.1 + 2)) ∨ (a.1 = b.1 ∧ a.2 ≠ b.2) instance not_cop_win_two_of_dominating_cycle_petersen_adj_decidable : DecidableRel not_cop_win_two_of_dominating_cycle_petersen_adj := fun a b => by unfold not_cop_win_two_of_dominating_cycle_petersen_adj infer_instance theorem not_cop_win_two_of_dominating_cycle_petersen_adj_symm : Std.Symm not_cop_win_two_of_dominating_cycle_petersen_adj := ⟨by decide⟩ theorem not_cop_win_two_of_dominating_cycle_petersen_adj_irrefl : Std.Irrefl not_cop_win_two_of_dominating_cycle_petersen_adj := ⟨by decide⟩ /-- The Petersen graph on `Fin 5 × Bool`: `(i, false)` on the outer 5-cycle, `(i, true)` on the inner pentagram, and a spoke joining `(i, false)` to `(i, true)`. -/ def not_cop_win_two_of_dominating_cycle_petersen : SimpleGraph (Fin 5 × Bool) := ⟨not_cop_win_two_of_dominating_cycle_petersen_adj, not_cop_win_two_of_dominating_cycle_petersen_adj_symm, not_cop_win_two_of_dominating_cycle_petersen_adj_irrefl⟩ instance not_cop_win_two_of_dominating_cycle_petersen_decidable_adj : DecidableRel not_cop_win_two_of_dominating_cycle_petersen.Adj := not_cop_win_two_of_dominating_cycle_petersen_adj_decidable /-- A cop/robber position is safe when the robber is neither on nor adjacent to any cop. -/ def not_cop_win_two_of_dominating_cycle_robber_safe (C : Fin 2 → Fin 5 × Bool) (R : Fin 5 × Bool) : Prop := ∀ i, C i ≠ R ∧ ¬ not_cop_win_two_of_dominating_cycle_petersen.Adj (C i) R instance not_cop_win_two_of_dominating_cycle_robber_safe_decidable (C : Fin 2 → Fin 5 × Bool) (R : Fin 5 × Bool) : Decidable (not_cop_win_two_of_dominating_cycle_robber_safe C R) := by unfold not_cop_win_two_of_dominating_cycle_robber_safe infer_instance /-- Every two-cop position on the Petersen graph leaves a safe robber position. -/ theorem not_cop_win_two_of_dominating_cycle_exists_robber_safe : ∀ C : Fin 2 → Fin 5 × Bool, ∃ R, not_cop_win_two_of_dominating_cycle_robber_safe C R := by decide /-- Safety is preserved: after any cop move there is a robber move restoring safety. -/ theorem not_cop_win_two_of_dominating_cycle_robber_safe_step : ∀ (C : Fin 2 → Fin 5 × Bool) (R : Fin 5 × Bool), not_cop_win_two_of_dominating_cycle_robber_safe C R → ∀ (C' : Fin 2 → Fin 5 × Bool), (∀ i, C' i = C i ∨ not_cop_win_two_of_dominating_cycle_petersen.Adj (C i) (C' i)) → ∃ R', (R' = R ∨ not_cop_win_two_of_dominating_cycle_petersen.Adj R R') ∧ not_cop_win_two_of_dominating_cycle_robber_safe C' R' := by decide /-- From a safe position the two cops never force a capture. -/ theorem not_cop_win_two_of_dominating_cycle_not_cops_win_from_safe : ∀ (C : Fin 2 → Fin 5 × Bool) (R : Fin 5 × Bool), not_cop_win_two_of_dominating_cycle_robber_safe C R → ¬ CopsCanWinFrom not_cop_win_two_of_dominating_cycle_petersen 2 C R := by intro C R hS hwin revert hS induction hwin with | capture C R hcap => intro hS obtain ⟨i, hi⟩ := hcap exact (hS i).1 hi | step_capture C R C' hC hcap => intro hS obtain ⟨i, hi⟩ := hcap rcases hC i with h | h · exact (hS i).1 (h.symm.trans hi) · exact (hS i).2 (hi ▸ h) | step C R C' hC hR ih => intro hS obtain ⟨R', hR', hS'⟩ := not_cop_win_two_of_dominating_cycle_robber_safe_step C R hS C' hC exact ih R' hR' hS' /-- Two cops do not have a winning strategy on the Petersen graph. -/ theorem not_cop_win_two_of_dominating_cycle_petersen_not_has_cop_win_two : ¬ HasCopWinStrategy not_cop_win_two_of_dominating_cycle_petersen 2 := by rintro ⟨C₀, h⟩ obtain ⟨R₀, hS⟩ := not_cop_win_two_of_dominating_cycle_exists_robber_safe C₀ exact not_cop_win_two_of_dominating_cycle_not_cops_win_from_safe C₀ R₀ hS (h R₀) /-- The outer 5-cycle of the Petersen graph, as a vertex map. -/ def not_cop_win_two_of_dominating_cycle_outer_vertex (i : Fin 5) : Fin 5 × Bool := (i, false) theorem not_cop_win_two_of_dominating_cycle_outer_vertex_injective : Function.Injective not_cop_win_two_of_dominating_cycle_outer_vertex := by intro a b h simpa [not_cop_win_two_of_dominating_cycle_outer_vertex] using h theorem not_cop_win_two_of_dominating_cycle_outer_vertex_adj_iff (a b : Fin 5) : not_cop_win_two_of_dominating_cycle_petersen.Adj (not_cop_win_two_of_dominating_cycle_outer_vertex a) (not_cop_win_two_of_dominating_cycle_outer_vertex b) ↔ (SimpleGraph.cycleGraph 5).Adj a b := by unfold not_cop_win_two_of_dominating_cycle_outer_vertex fin_cases a <;> fin_cases b <;> decide /-- The outer 5-cycle of the Petersen graph is an embedded copy of `cycleGraph 5`. -/ def not_cop_win_two_of_dominating_cycle_outer_cycle_embedding : SimpleGraph.cycleGraph 5 ↪g not_cop_win_two_of_dominating_cycle_petersen := RelEmbedding.mk ⟨not_cop_win_two_of_dominating_cycle_outer_vertex, not_cop_win_two_of_dominating_cycle_outer_vertex_injective⟩ (by intro a b; exact not_cop_win_two_of_dominating_cycle_outer_vertex_adj_iff a b) /-- The outer 5-cycle dominates the Petersen graph. -/ theorem not_cop_win_two_of_dominating_cycle_outer_cycle_dominates : simple_graph_is_dominating not_cop_win_two_of_dominating_cycle_petersen (Set.range not_cop_win_two_of_dominating_cycle_outer_cycle_embedding) := by intro v obtain ⟨a, b⟩ := v cases b · exact Or.inl ⟨a, rfl⟩ · exact Or.inr ⟨(a, false), ⟨a, rfl⟩, Or.inr (Or.inr ⟨rfl, Bool.false_ne_true⟩)⟩ /-- The cop game is invariant under an equivalence of graphs: positions transport along `e`. -/ theorem not_cop_win_two_of_dominating_cycle_cops_win_from_equiv {V W : Type*} {G : SimpleGraph V} {G' : SimpleGraph W} (e : V ≃ W) (hadj : ∀ a b, G'.Adj (e a) (e b) ↔ G.Adj a b) : ∀ (c : ℕ) (C : Fin c → V) (R : V), CopsCanWinFrom G c C R → CopsCanWinFrom G' c (fun i => e (C i)) (e R) := by intro c C R h induction h with | capture C R hcap => obtain ⟨i, hi⟩ := hcap exact CopsCanWinFrom.capture _ _ ⟨i, by rw [hi]⟩ | step_capture C R C' hC hcap => obtain ⟨i, hi⟩ := hcap refine CopsCanWinFrom.step_capture _ _ (fun i => e (C' i)) ?_ ⟨i, by rw [hi]⟩ intro i rcases hC i with h | h · exact Or.inl (by rw [h]) · exact Or.inr ((hadj (C i) (C' i)).mpr h) | step C R C' hC hR ih => refine CopsCanWinFrom.step _ _ (fun i => e (C' i)) ?_ ?_ · intro i rcases hC i with h | h · exact Or.inl (by rw [h]) · exact Or.inr ((hadj (C i) (C' i)).mpr h) · intro R' hR' rcases hR' with h | h · rw [h] exact ih R (Or.inl rfl) · have h' : G'.Adj (e R) (e (e.symm R')) := by rw [Equiv.apply_symm_apply]; exact h simpa using ih (e.symm R') (Or.inr ((hadj R (e.symm R')).mp h')) /-- The Petersen graph lifted to an arbitrary universe. -/ def not_cop_win_two_of_dominating_cycle_ulift_petersen : SimpleGraph (ULift (Fin 5 × Bool)) where Adj a b := not_cop_win_two_of_dominating_cycle_petersen.Adj a.down b.down symm := ⟨fun a b h => (SimpleGraph.symm not_cop_win_two_of_dominating_cycle_petersen).symm a.down b.down h⟩ loopless := ⟨fun a h => (SimpleGraph.loopless not_cop_win_two_of_dominating_cycle_petersen).irrefl a.down h⟩ /-- Two cops do not win on the universe-lifted Petersen graph either. -/ theorem not_cop_win_two_of_dominating_cycle_ulift_not_has_cop_win_two : ¬ HasCopWinStrategy not_cop_win_two_of_dominating_cycle_ulift_petersen 2 := by rintro ⟨C₀, hC⟩ refine not_cop_win_two_of_dominating_cycle_petersen_not_has_cop_win_two ⟨fun i => (C₀ i).down, ?_⟩ intro R exact not_cop_win_two_of_dominating_cycle_cops_win_from_equiv (G := not_cop_win_two_of_dominating_cycle_ulift_petersen) (G' := not_cop_win_two_of_dominating_cycle_petersen) (e := Equiv.ulift) (fun a b => Iff.rfl) 2 C₀ (ULift.up R) (hC (ULift.up R)) /-- The universe-lifted outer 5-cycle vertex map. -/ def not_cop_win_two_of_dominating_cycle_ulift_outer_vertex : Fin 5 → ULift (Fin 5 × Bool) := fun i => ULift.up (not_cop_win_two_of_dominating_cycle_outer_vertex i) theorem not_cop_win_two_of_dominating_cycle_ulift_outer_vertex_injective : Function.Injective not_cop_win_two_of_dominating_cycle_ulift_outer_vertex := by intro a b h have h2 : (a, false) = (b, false) := ULift.up_inj.mp h simpa using h2 theorem not_cop_win_two_of_dominating_cycle_ulift_outer_vertex_adj_iff (a b : Fin 5) : not_cop_win_two_of_dominating_cycle_ulift_petersen.Adj (not_cop_win_two_of_dominating_cycle_ulift_outer_vertex a) (not_cop_win_two_of_dominating_cycle_ulift_outer_vertex b) ↔ (SimpleGraph.cycleGraph 5).Adj a b := by show not_cop_win_two_of_dominating_cycle_petersen_adj (a, false) (b, false) ↔ (SimpleGraph.cycleGraph 5).Adj a b fin_cases a <;> fin_cases b <;> decide /-- The outer 5-cycle inside the universe-lifted Petersen graph. -/ def not_cop_win_two_of_dominating_cycle_ulift_outer_cycle_embedding : SimpleGraph.cycleGraph 5 ↪g not_cop_win_two_of_dominating_cycle_ulift_petersen := RelEmbedding.mk ⟨not_cop_win_two_of_dominating_cycle_ulift_outer_vertex, not_cop_win_two_of_dominating_cycle_ulift_outer_vertex_injective⟩ (by intro a b; exact not_cop_win_two_of_dominating_cycle_ulift_outer_vertex_adj_iff a b) /-- The outer 5-cycle dominates the universe-lifted Petersen graph. -/ theorem not_cop_win_two_of_dominating_cycle_ulift_outer_cycle_dominates : simple_graph_is_dominating not_cop_win_two_of_dominating_cycle_ulift_petersen (Set.range not_cop_win_two_of_dominating_cycle_ulift_outer_cycle_embedding) := by intro v cases v with | up x => obtain ⟨a, b⟩ := x cases b · exact Or.inl ⟨a, rfl⟩ · exact Or.inr ⟨ULift.up (a, false), ⟨a, rfl⟩, Or.inr (Or.inr ⟨rfl, Bool.false_ne_true⟩)⟩ theorem not_cop_win_two_of_dominating_cycle : ¬ (∀ {V : Type*} [Fintype V] (G : SimpleGraph V) (m : ℕ) (hm : 3 ≤ m) (f : SimpleGraph.cycleGraph m ↪g G) (hdom : simple_graph_is_dominating G (Set.range f)), HasCopWinStrategy G 2) := by intro h exact not_cop_win_two_of_dominating_cycle_ulift_not_has_cop_win_two (h (V := ULift (Fin 5 × Bool)) (G := not_cop_win_two_of_dominating_cycle_ulift_petersen) (m := 5) (hm := by norm_num) (f := not_cop_win_two_of_dominating_cycle_ulift_outer_cycle_embedding) (hdom := not_cop_win_two_of_dominating_cycle_ulift_outer_cycle_dominates))