not_is_pk_free_claw_free_hole_dominating
The statement is_pk_free_claw_free_hole_dominating is false: The statement is false as written: it allows k = 4 and m = 3 (since k - 1 = 3 ≤ 3). Counterexample: start from K4 on vertices {0,1,2,3} and attach a pendant vertex 4 adjacent only to 3 (i.e. the "paw"-like graph H = K4 with a pendant edge). Call it cex.
* cex is connected (0,1,2,3 form a clique and 4 is adjacent to 3).
* cex is P4-free: any induced P4 would need four vertices inducing a path; any four of {0,1,2,3} induce K4 minus at most one edge (contains a triangle, so not a path), and including vertex 4 (degree 1, neighbour 3 which is adjacent to everything else) always produces an induced P3 at most — checked exhaustively by decide over all injections Fin 4 → Fin 5.
* cex is claw-free: the claw needs a vertex with three pairwise non-adjacent neighbours; every vertex of cex has neighbourhood inducing a clique or a single edge — again checked exhaustively by decide over all injections Fin 1 ⊕ Fin 3 → Fin 5.
* The triangle {0,1,2} is an induced cycle C3 (embedding f5 of cycleGraph 3), and it is not dominating: vertex 4 is not in {0,1,2} and its only neighbour is 3, which is not in {0,1,2}.
So all hypotheses hold with k = 4, m = 3, yet simple_graph_is_dominating cex (Set.range f5) fails. The informal source presumably requires the hole to have length ≥ k (or k - 2 with a different constant, or the graph to be Claw-free AND P_k-free with k ≥ 5 plus the hole length being at least k - 1 meaning m ≥ k - 1 with m ≥ 5...). Note that for k = 4, k - 1 = 3, and triangles are never "long", so the bound k - 1 must be at least 5 (or m must be required to be ≥ k, since the argument uses an induced path on k vertices built from the hole plus a vertex at distance 2 from it, which needs the hole to have at least k - 1 vertices... actually the derivation needs a vertex outside the hole at distance exactly 2, and then the hole contributes 3 consecutive vertices, giving a P5 = k, which is why k ≥ 5 must be assumed).
Statement
theorem not_is_pk_free_claw_free_hole_dominating : ¬ (∀ {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (k m : ℕ) (hk : IsPkFree G k) (hclaw : IsClawFree G) (hm : k - 1 ≤ m) (f : SimpleGraph.cycleGraph m ↪g G), simple_graph_is_dominating G (Set.range f))
- Related work
- refutes `is_pk_free_claw_free_hole_dominating`
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- is_claw_free_triple_neighborsIn any claw-free graph, among any three distinct neighbors of a vertex, at least two are adjacent.
- IsClawFreeA simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
- 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.
- IsPkFreeA simple graph G is P_k-free if it contains no induced subgraph isomorphic to the path on k vertices.
- Arena.Reachable.transReachability is transitive.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
The proof, explained
The statement asserts that in any connected, claw-free, and P_k-free graph, every induced cycle of length m ≥ k - 1 is a dominating set. This is disproved by setting k = 4 and m = 3 on a 5-vertex counterexample graph formed by a 4-clique on {0, 1, 2, 3} with a pendant vertex 4 attached to 3. Finite exhaustive checks confirm that this graph is connected, P₄-free, and claw-free, and that {0, 1, 2} induces a cycle C₃ satisfying k - 1 = 3 ≤ m. However, this triangle fails to dominate vertex 4, because 4 is neither in {0, 1, 2} nor adjacent to any vertex in {0, 1, 2}.
Adjacency in the counterexample graph and in the claw graph K₁,₃ is decidable.
Both adjacency relations are defined using propositional connectives and equalities over finite sets, allowing their decidability instances to be resolved by unfolding definitions and typeclass synthesis.
instance not_is_pk_free_claw_free_hole_dominating_cex_decRel : DecidableRel not_is_pk_free_claw_free_hole_dominating_cex.Adj := by intro a b; unfold not_is_pk_free_claw_free_hole_dominating_cex; infer_instance instance not_is_pk_free_claw_free_hole_dominating_bip_decRel : DecidableRel (completeBipartiteGraph (Fin 1) (Fin 3)).Adj := by intro a b; unfold completeBipartiteGraph; infer_instance
The vertex mapping from the 3-cycle into the 5-vertex counterexample graph is well-defined and injective.
Each index i ∈ Fin 3 maps to the corresponding vertex in Fin 5, with i < 5 verified by linear arithmetic (`omega`). Injectivity follows because equality of the lifted Fin 5 values implies equality of the underlying natural numbers (`ULift.up_injective`, `congrArg`).
uses
ULift.up_injective,congrArgdef not_is_pk_free_claw_free_hole_dominating_toFun : Fin 3 → ULift.{u,0} (Fin 5) := fun i => ULift.up ⟨i.val, by omega⟩ lemma not_is_pk_free_claw_free_hole_dominating_toFun_inj : Function.Injective not_is_pk_free_claw_free_hole_dominating_toFun := by intro a b h have h' := ULift.up_injective h ext simpa using congrArg Fin.val h'
The vertices {0, 1, 2} induce a cycle C₃ in the counterexample graph.
For every pair of vertices in {0, 1, 2}, adjacency in the counterexample graph matches adjacency in C₃, verified by exhaustive evaluation (`decide`). The injective vertex map and adjacency equivalence are packaged into an induced subgraph embedding.
uses
not_is_pk_free_claw_free_hole_dominating_toFun_inj,not_is_pk_free_claw_free_hole_dominating_rel_ifflemma not_is_pk_free_claw_free_hole_dominating_rel_iff : ∀ a b : Fin 3, not_is_pk_free_claw_free_hole_dominating_cex.Adj (not_is_pk_free_claw_free_hole_dominating_toFun a) (not_is_pk_free_claw_free_hole_dominating_toFun b) ↔ (cycleGraph 3).Adj a b := by decide /-- The triangle `{0,1,2}` as an induced cycle in the counterexample. -/ def not_is_pk_free_claw_free_hole_dominating_emb : SimpleGraph.cycleGraph 3 ↪g not_is_pk_free_claw_free_hole_dominating_cex := RelEmbedding.mk ⟨not_is_pk_free_claw_free_hole_dominating_toFun, not_is_pk_free_claw_free_hole_dominating_toFun_inj⟩ (by intro a b; exact not_is_pk_free_claw_free_hole_dominating_rel_iff a b)
Consecutive vertices along the path 0-1-2-3-4 are adjacent. automation
For each index i ∈ {0, 1, 2, 3}, the edge between i and i + 1 is checked by case analysis on i followed by computational evaluation (`decide`).
lemma not_is_pk_free_claw_free_hole_dominating_step : ∀ i : Fin 4, not_is_pk_free_claw_free_hole_dominating_cex.Adj (ULift.up (Fin.castSucc i)) (ULift.up i.succ) := by intro i; fin_cases i <;> decide
Vertex 0 can reach every vertex in the counterexample graph.
Explicit walks from vertex 0 to each vertex k ∈ {0, 1, 2, 3, 4} are constructed by concatenating the step edges (0, 1), (1, 2), (2, 3), and (3, 4) using `SimpleGraph.Walk.cons` and `SimpleGraph.Walk.nil`, with vertex 0 reaching itself by reflexivity (`SimpleGraph.Reachable.refl`).
uses
SimpleGraph.Reachable.refl,SimpleGraph.Walk.cons,SimpleGraph.Walk.nil,not_is_pk_free_claw_free_hole_dominating_steplemma not_is_pk_free_claw_free_hole_dominating_reach : ∀ k : Fin 5, not_is_pk_free_claw_free_hole_dominating_cex.Reachable (ULift.up (0 : Fin 5)) (ULift.up k) := by intro k fin_cases k · exact SimpleGraph.Reachable.refl _ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) SimpleGraph.Walk.nil⟩ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 1) SimpleGraph.Walk.nil)⟩ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 1) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 2) SimpleGraph.Walk.nil))⟩ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 1) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 2) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 3) SimpleGraph.Walk.nil)))⟩
The counterexample graph is connected.
Preconnectedness holds because any two vertices a and b are linked via vertex 0: reversing the walk from 0 to a and composing it with the walk from 0 to b yields a walk from a to b. Nonemptiness is witnessed by vertex 0.
uses
not_is_pk_free_claw_free_hole_dominating_reachlemma not_is_pk_free_claw_free_hole_dominating_connected : not_is_pk_free_claw_free_hole_dominating_cex.Connected where preconnected := by rintro ⟨a⟩ ⟨b⟩ exact (not_is_pk_free_claw_free_hole_dominating_reach a).symm.trans (not_is_pk_free_claw_free_hole_dominating_reach b) nonempty := ⟨ULift.up (0:Fin 5)⟩
No 4-vertex map into the counterexample graph induces a path P₄. automation
The `decide` tactic checks all 5⁴ = 625 mappings from Fin 4 to Fin 5, verifying by exhaustive computation that none of them preserves and reflects the adjacency relation of the path graph P₄.
lemma not_is_pk_free_claw_free_hole_dominating_no_pk_embed : ∀ g : Fin 4 → ULift.{u,0} (Fin 5), ¬ (∀ a b : Fin 4, not_is_pk_free_claw_free_hole_dominating_cex.Adj (g a) (g b) ↔ ((a:ℕ)+1 = (b:ℕ) ∨ (b:ℕ)+1 = (a:ℕ))) := by decide
No injective map from K₁,₃ into the counterexample graph induces a claw. automation
The `decide` tactic exhaustively checks every injective mapping from the 4 vertices of K₁,₃ into Fin 5, verifying that none induces the complete bipartite claw graph.
lemma not_is_pk_free_claw_free_hole_dominating_no_claw_embed : ∀ g : Fin 1 ⊕ Fin 3 → ULift.{u,0} (Fin 5), Function.Injective g → ¬ (∀ a b, not_is_pk_free_claw_free_hole_dominating_cex.Adj (g a) (g b) ↔ (completeBipartiteGraph (Fin 1) (Fin 3)).Adj a b) := by decide
The counterexample graph is P₄-free.
An induced path P₄ would provide an embedding whose vertex map preserves the path adjacency condition (`SimpleGraph.pathGraph_adj`), directly contradicting the exhaustive non-existence lemma `not_is_pk_free_claw_free_hole_dominating_no_pk_embed`.
uses
not_is_pk_free_claw_free_hole_dominating_no_pk_embed,SimpleGraph.pathGraph_adjlemma not_is_pk_free_claw_free_hole_dominating_pk_free_four : IsPkFree not_is_pk_free_claw_free_hole_dominating_cex 4 := by rintro ⟨f⟩ exact not_is_pk_free_claw_free_hole_dominating_no_pk_embed f.toFun (fun a b => f.map_rel_iff'.trans SimpleGraph.pathGraph_adj)
The counterexample graph is claw-free.
An induced claw would provide an injective relation embedding from K₁,₃ into the graph, contradicting the exhaustive check `not_is_pk_free_claw_free_hole_dominating_no_claw_embed`.
uses
not_is_pk_free_claw_free_hole_dominating_no_claw_embedlemma not_is_pk_free_claw_free_hole_dominating_claw_free : IsClawFree not_is_pk_free_claw_free_hole_dominating_cex := by rintro ⟨f⟩ exact not_is_pk_free_claw_free_hole_dominating_no_claw_embed f.toFun f.inj' (fun a b => f.map_rel_iff')
Vertex 4 is not in the embedded 3-cycle {0, 1, 2}.
Rewriting non-membership with `Set.mem_range` and `not_exists` reduces the claim to verifying that no index i ∈ {0, 1, 2} maps to vertex 4, which is checked by case exhaustion (`fin_cases i <;> decide`).
uses
Set.mem_range,not_existslemma not_is_pk_free_claw_free_hole_dominating_emb_not_mem : (ULift.up (4:Fin 5) : ULift.{u,0} (Fin 5)) ∉ Set.range not_is_pk_free_claw_free_hole_dominating_emb := by simp only [Set.mem_range, not_exists] intro i fin_cases i <;> decide
Vertex 4 has no neighbour in the embedded 3-cycle {0, 1, 2}. automation
Case analysis on each of the vertices 0, 1, 2 confirms by computation (`decide`) that none is adjacent to vertex 4, as the only neighbour of 4 in the graph is 3.
lemma not_is_pk_free_claw_free_hole_dominating_emb_no_adj : ∀ i : Fin 3, ¬ not_is_pk_free_claw_free_hole_dominating_cex.Adj (not_is_pk_free_claw_free_hole_dominating_emb i) (ULift.up (4:Fin 5)) := by intro i fin_cases i <;> decide
Under the assumed theorem, the triangle {0, 1, 2} would be a dominating set.
Assuming the universal statement for contradiction (`intro h`), specialize it to the counterexample graph with parameters k = 4 and m = 3. The graph is connected (`not_is_pk_free_claw_free_hole_dominating_connected`), P₄-free (`not_is_pk_free_claw_free_hole_dominating_pk_free_four`), claw-free (`not_is_pk_free_claw_free_hole_dominating_claw_free`), satisfies the length requirement 4 - 1 ≤ 3 (by `norm_num`), and has the induced cycle embedding {0, 1, 2} (`not_is_pk_free_claw_free_hole_dominating_emb`). Hence the statement yields that the triangle is dominating.
uses
not_is_pk_free_claw_free_hole_dominating_connected,not_is_pk_free_claw_free_hole_dominating_pk_free_four,not_is_pk_free_claw_free_hole_dominating_claw_free,not_is_pk_free_claw_free_hole_dominating_embtheorem not_is_pk_free_claw_free_hole_dominating : ¬ (∀ {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (k m : ℕ) (hk : IsPkFree G k) (hclaw : IsClawFree G) (hm : k - 1 ≤ m) (f : SimpleGraph.cycleGraph m ↪g G), simple_graph_is_dominating G (Set.range f)) := by intro h have hdom : simple_graph_is_dominating not_is_pk_free_claw_free_hole_dominating_cex (Set.range not_is_pk_free_claw_free_hole_dominating_emb) := h (V := ULift (Fin 5)) not_is_pk_free_claw_free_hole_dominating_cex not_is_pk_free_claw_free_hole_dominating_connected 4 3 not_is_pk_free_claw_free_hole_dominating_pk_free_four not_is_pk_free_claw_free_hole_dominating_claw_free (by norm_num) not_is_pk_free_claw_free_hole_dominating_emb
Domination fails at vertex 4, completing the refutation.
By definition of a dominating set, vertex 4 must either belong to the triangle {0, 1, 2} or be adjacent to some vertex in it. The first case is ruled out by `not_is_pk_free_claw_free_hole_dominating_emb_not_mem`, and the second case is ruled out by `not_is_pk_free_claw_free_hole_dominating_emb_no_adj`. Both cases lead to a contradiction, refuting the theorem.
uses
not_is_pk_free_claw_free_hole_dominating_emb_not_mem,not_is_pk_free_claw_free_hole_dominating_emb_no_adjrcases hdom (ULift.up (4:Fin 5)) with hmem | ⟨w, ⟨i, hi⟩, hadj⟩ · exact not_is_pk_free_claw_free_hole_dominating_emb_not_mem hmem · exact not_is_pk_free_claw_free_hole_dominating_emb_no_adj i (hi.symm ▸ hadj)
congrArg- Applying a function to equal arguments yields equal values: if a₁ = a₂, then f(a₁) = f(a₂).
completeBipartiteGraph- The complete bipartite graph with 1 vertex on one side and 3 on the other (the claw graph K₁,₃).
ULift.up_injective- The constructor ULift.up is injective, so ULift.up a = ULift.up b implies a = b.
not_is_pk_free_claw_free_hole_dominating_toFun_inj- The embedding of the 3-cycle C₃ into the counterexample graph sending vertices to {0, 1, 2} is injective.
not_is_pk_free_claw_free_hole_dominating_rel_iff- Two vertices in {0, 1, 2} are adjacent in the counterexample graph if and only if they are adjacent in the cycle graph C₃.
not_is_pk_free_claw_free_hole_dominating_step- Each consecutive pair (i, i + 1) for i ∈ {0, 1, 2, 3} is adjacent in the counterexample graph.
SimpleGraph.Reachable.refl- Every vertex is reachable from itself in zero steps.
SimpleGraph.Walk.cons- Prepending an edge (u, v) to a walk from v to w yields a walk from u to w.
SimpleGraph.Walk.nil- The trivial walk from any vertex to itself containing no edges.
not_is_pk_free_claw_free_hole_dominating_reach- Vertex 0 can reach every vertex k ∈ {0, 1, 2, 3, 4} in the counterexample graph.
not_is_pk_free_claw_free_hole_dominating_connected- The counterexample graph on 5 vertices is connected.
not_is_pk_free_claw_free_hole_dominating_no_pk_embed- No mapping from the 4 vertices of a path graph into the counterexample graph induces a path P₄.
SimpleGraph.pathGraph_adj- Two vertices in the path graph Pₙ are adjacent if and only if their natural number indices differ by 1.
not_is_pk_free_claw_free_hole_dominating_no_claw_embed- No injective mapping from the vertices of the claw K₁,₃ into the counterexample graph induces a claw.
not_is_pk_free_claw_free_hole_dominating_pk_free_four- The counterexample graph contains no induced path on 4 vertices (it is P₄-free).
not_is_pk_free_claw_free_hole_dominating_claw_free- The counterexample graph contains no induced claw K₁,₃ (it is claw-free).
Set.mem_range- An element x belongs to the range of f if and only if there exists y such that f(y) = x.
not_exists- Negation distributes over existential quantification: ¬(∃ x, P x) is equivalent to ∀ x, ¬P x.
not_is_pk_free_claw_free_hole_dominating_emb_not_mem- Vertex 4 does not belong to the range of the embedding of the 3-cycle {0, 1, 2}.
not_is_pk_free_claw_free_hole_dominating_emb_no_adj- Vertex 4 is not adjacent to any vertex in the embedded 3-cycle {0, 1, 2}.
not_is_pk_free_claw_free_hole_dominating_emb- The induced cycle embedding of C₃ into the counterexample graph with image {0, 1, 2}.
- The absence of induced P₄ paths and induced claws in the 5-vertex graph is established by the `decide` tactic, which exhaustively checks all mappings from Fin 4 and Fin 1 ⊕ Fin 3 into the 5-element vertex set.
- The universe lift `ULift (Fin 5)` is a formal Lean construction to place the 5-vertex graph into an arbitrary universe `u`, matching the universe quantification in the theorem statement.
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.
open SimpleGraphuniverse u/-- The counterexample graph: `K4` on `{0,1,2,3}` together with a pendant vertex `4` attached to `3`. -/def not_is_pk_free_claw_free_hole_dominating_cex : SimpleGraph (ULift.{u,0} (Fin 5)) where Adj a b := (a ≠ b) ∧ (a = ULift.up (4 : Fin 5) → b = ULift.up (3 : Fin 5)) ∧ (b = ULift.up (4 : Fin 5) → a = ULift.up (3 : Fin 5)) symm := ⟨fun _ _ h => ⟨h.1.symm, h.2.2, h.2.1⟩⟩ loopless := ⟨fun _ h => h.1 rfl⟩instance not_is_pk_free_claw_free_hole_dominating_cex_decRel : DecidableRel not_is_pk_free_claw_free_hole_dominating_cex.Adj := by intro a b; unfold not_is_pk_free_claw_free_hole_dominating_cex; infer_instanceinstance not_is_pk_free_claw_free_hole_dominating_bip_decRel : DecidableRel (completeBipartiteGraph (Fin 1) (Fin 3)).Adj := by intro a b; unfold completeBipartiteGraph; infer_instance/-- The embedding of the triangle `C₃` into the counterexample. -/def not_is_pk_free_claw_free_hole_dominating_toFun : Fin 3 → ULift.{u,0} (Fin 5) := fun i => ULift.up ⟨i.val, by omega⟩lemma not_is_pk_free_claw_free_hole_dominating_toFun_inj : Function.Injective not_is_pk_free_claw_free_hole_dominating_toFun := by intro a b h have h' := ULift.up_injective h ext simpa using congrArg Fin.val h'lemma not_is_pk_free_claw_free_hole_dominating_rel_iff : ∀ a b : Fin 3, not_is_pk_free_claw_free_hole_dominating_cex.Adj (not_is_pk_free_claw_free_hole_dominating_toFun a) (not_is_pk_free_claw_free_hole_dominating_toFun b) ↔ (cycleGraph 3).Adj a b := by decide/-- The triangle `{0,1,2}` as an induced cycle in the counterexample. -/def not_is_pk_free_claw_free_hole_dominating_emb : SimpleGraph.cycleGraph 3 ↪g not_is_pk_free_claw_free_hole_dominating_cex := RelEmbedding.mk ⟨not_is_pk_free_claw_free_hole_dominating_toFun, not_is_pk_free_claw_free_hole_dominating_toFun_inj⟩ (by intro a b; exact not_is_pk_free_claw_free_hole_dominating_rel_iff a b)lemma not_is_pk_free_claw_free_hole_dominating_step : ∀ i : Fin 4, not_is_pk_free_claw_free_hole_dominating_cex.Adj (ULift.up (Fin.castSucc i)) (ULift.up i.succ) := by intro i; fin_cases i <;> decidelemma not_is_pk_free_claw_free_hole_dominating_reach : ∀ k : Fin 5, not_is_pk_free_claw_free_hole_dominating_cex.Reachable (ULift.up (0 : Fin 5)) (ULift.up k) := by intro k fin_cases k · exact SimpleGraph.Reachable.refl _ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) SimpleGraph.Walk.nil⟩ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 1) SimpleGraph.Walk.nil)⟩ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 1) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 2) SimpleGraph.Walk.nil))⟩ · exact ⟨SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 0) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 1) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 2) (SimpleGraph.Walk.cons (not_is_pk_free_claw_free_hole_dominating_step 3) SimpleGraph.Walk.nil)))⟩lemma not_is_pk_free_claw_free_hole_dominating_connected : not_is_pk_free_claw_free_hole_dominating_cex.Connected where preconnected := by rintro ⟨a⟩ ⟨b⟩ exact (not_is_pk_free_claw_free_hole_dominating_reach a).symm.trans (not_is_pk_free_claw_free_hole_dominating_reach b) nonempty := ⟨ULift.up (0:Fin 5)⟩lemma not_is_pk_free_claw_free_hole_dominating_no_pk_embed : ∀ g : Fin 4 → ULift.{u,0} (Fin 5), ¬ (∀ a b : Fin 4, not_is_pk_free_claw_free_hole_dominating_cex.Adj (g a) (g b) ↔ ((a:ℕ)+1 = (b:ℕ) ∨ (b:ℕ)+1 = (a:ℕ))) := by decidelemma not_is_pk_free_claw_free_hole_dominating_no_claw_embed : ∀ g : Fin 1 ⊕ Fin 3 → ULift.{u,0} (Fin 5), Function.Injective g → ¬ (∀ a b, not_is_pk_free_claw_free_hole_dominating_cex.Adj (g a) (g b) ↔ (completeBipartiteGraph (Fin 1) (Fin 3)).Adj a b) := by decidelemma not_is_pk_free_claw_free_hole_dominating_pk_free_four : IsPkFree not_is_pk_free_claw_free_hole_dominating_cex 4 := by rintro ⟨f⟩ exact not_is_pk_free_claw_free_hole_dominating_no_pk_embed f.toFun (fun a b => f.map_rel_iff'.trans SimpleGraph.pathGraph_adj)lemma not_is_pk_free_claw_free_hole_dominating_claw_free : IsClawFree not_is_pk_free_claw_free_hole_dominating_cex := by rintro ⟨f⟩ exact not_is_pk_free_claw_free_hole_dominating_no_claw_embed f.toFun f.inj' (fun a b => f.map_rel_iff')lemma not_is_pk_free_claw_free_hole_dominating_emb_not_mem : (ULift.up (4:Fin 5) : ULift.{u,0} (Fin 5)) ∉ Set.range not_is_pk_free_claw_free_hole_dominating_emb := by simp only [Set.mem_range, not_exists] intro i fin_cases i <;> decidelemma not_is_pk_free_claw_free_hole_dominating_emb_no_adj : ∀ i : Fin 3, ¬ not_is_pk_free_claw_free_hole_dominating_cex.Adj (not_is_pk_free_claw_free_hole_dominating_emb i) (ULift.up (4:Fin 5)) := by intro i fin_cases i <;> decidetheorem not_is_pk_free_claw_free_hole_dominating : ¬ (∀ {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (k m : ℕ) (hk : IsPkFree G k) (hclaw : IsClawFree G) (hm : k - 1 ≤ m) (f : SimpleGraph.cycleGraph m ↪g G), simple_graph_is_dominating G (Set.range f)) := by intro h have hdom : simple_graph_is_dominating not_is_pk_free_claw_free_hole_dominating_cex (Set.range not_is_pk_free_claw_free_hole_dominating_emb) := h (V := ULift (Fin 5)) not_is_pk_free_claw_free_hole_dominating_cex not_is_pk_free_claw_free_hole_dominating_connected 4 3 not_is_pk_free_claw_free_hole_dominating_pk_free_four not_is_pk_free_claw_free_hole_dominating_claw_free (by norm_num) not_is_pk_free_claw_free_hole_dominating_emb rcases hdom (ULift.up (4:Fin 5)) with hmem | ⟨w, ⟨i, hi⟩, hadj⟩ · exact not_is_pk_free_claw_free_hole_dominating_emb_not_mem hmem · exact not_is_pk_free_claw_free_hole_dominating_emb_no_adj i (hi.symm ▸ hadj)