AFTD Auto-Formalizing Theoretical Domains

not_is_pk_free_claw_free_hole_dominating

theoremverifiedoriginal

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}.

  1. 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.

    lines 11–18

    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
    
  2. 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`).

    lines 20–29

    uses ULift.up_injective, congrArg

    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'
    
  3. 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.

    lines 30–43

    uses not_is_pk_free_claw_free_hole_dominating_toFun_inj, not_is_pk_free_claw_free_hole_dominating_rel_iff

    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)
    
  4. 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`).

    lines 44–48

    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
    
  5. 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`).

    lines 49–69

    uses SimpleGraph.Reachable.refl, SimpleGraph.Walk.cons, SimpleGraph.Walk.nil, not_is_pk_free_claw_free_hole_dominating_step

    lemma 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)))⟩
    
  6. 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.

    lines 70–77

    uses not_is_pk_free_claw_free_hole_dominating_reach

    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)⟩
    
  7. 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₄.

    lines 78–84

    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
    
  8. 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.

    lines 85–91

    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
    
  9. 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`.

    lines 92–97

    uses not_is_pk_free_claw_free_hole_dominating_no_pk_embed, SimpleGraph.pathGraph_adj

    lemma 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)
    
  10. 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`.

    lines 98–103

    uses not_is_pk_free_claw_free_hole_dominating_no_claw_embed

    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')
    
  11. 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`).

    lines 104–110

    uses Set.mem_range, not_exists

    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 <;> decide
    
  12. 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.

    lines 111–117

    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
    
  13. 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.

    lines 118–128

    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_emb

    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)) := 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
  14. 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.

    lines 129–131

    uses not_is_pk_free_claw_free_hole_dominating_emb_not_mem, not_is_pk_free_claw_free_hole_dominating_emb_no_adj

      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)
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}.

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

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