AFTD Auto-Formalizing Theoretical Domains

not_p7_claw_free_dominating_pair_of_no_hole

theoremverifiedoriginal

The statement p7_claw_free_dominating_pair_of_no_hole is false: The statement is FALSE. A concrete counterexample is the net graph (a central triangle with a pendant vertex attached to each vertex of the triangle) on 6 vertices: - Vertex set: {0, 1, 2, 3, 4, 5}. - Edges: (0, 3), (0, 4), (0, 5), (1, 4), (2, 5), (4, 5). Verification of hypotheses: 1. Connected: The graph is connected (triangle {0, 4, 5} with leaves 1, 2, 3 attached). 2. IsPkFree G 7: The graph has only 6 vertices, so |V| < 7 implies it contains no induced P_7. 3. IsClawFree G: The only vertices of degree ≥ 3 are 0, 4, and 5. In each case, two of their three neighbors are mutually adjacent (forming the central triangle), so no vertex has an independent set of 3 neighbors. Thus G is claw-free. 4. ∀ m ≥ 6, IsEmpty (cycleGraph m ↪g G): The only cycle in G has length 3; there is no cycle of length ≥ 6 (for m > 6, |V| = 6 < m; for m = 6, degrees are 3, 3, 3, 1, 1, 1, so no 2-regular subgraph exists). Failure of conclusion: In G, every vertex has closed neighborhood of size at most 4 (the vertices 0, 4, 5 have closed neighborhoods of size 4; vertices 1, 2, 3 have closed neighborhoods of size 2). Every pair {u, v} leaves at least one leaf vertex uncovered: - {0, 4} does not dominate 2. - {0, 5} does not dominate 1. - {4, 5} does not dominate 3. - Any pair involving a leaf dominates strictly fewer vertices. Thus no dominating pair exists (the domination number of the net graph is 3).

Statement

theorem not_p7_claw_free_dominating_pair_of_no_hole : ¬ (∀ {V : Type*} [Fintype V] (G : SimpleGraph V)
    (hconn : G.Connected) (hp : IsPkFree G 7) (hclaw : IsClawFree G)
    (hno_hole : ∀ m ≥ 6, IsEmpty (SimpleGraph.cycleGraph m ↪g G)), ∃ u v : V, ∀ w : V, w = u ∨ w = v ∨ G.Adj u w ∨ G.Adj v w)
Related work
refutes `p7_claw_free_dominating_pair_of_no_hole`
Verified
27 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.
  • net_graphThe net graph on 6 vertices: the triangle {0,4,5} with a pendant leaf (3, 1, 2 respectively) attached to each triangle vertex; edges 03,…
  • IsClawFreeA simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
  • IsPkFreeA simple graph G is P_k-free if it contains no induced subgraph isomorphic to the path on k vertices.
  • is_pk_free_of_card_ltAny simple graph on fewer than k vertices is P_k-free, as an induced embedding requires an injection from Fin k into V.
  • Arena.Reachable.transReachability is transitive.

The proof, explained

The statement that every connected, P_7-free, claw-free graph with no induced cycle of length at least 6 possesses a dominating pair is disproved using the 6-vertex net graph as a counterexample. The net graph consists of a central triangle with one pendant leaf attached to each vertex. It is connected, has only 6 vertices so it trivially contains no induced P_7, is claw-free because no vertex has three mutually non-adjacent neighbors, and contains no induced C_m for m ≥ 6 because its leaves have degree 1 and its only cycle has length 3. Finally, exhaustive checking shows that every pair of vertices leaves at least one leaf vertex undominated, so no dominating pair exists.

  1. Adjacency in the net graph is equivalent to membership in the explicit list of twelve directed edges. automation

    We unfold the definition of the net graph and simplify the adjacency relation. Since the graph has only six vertices, exhaustive checking over all 36 pairs of vertices in Fin 6 verifies that adjacency matches the specified list of directed edges.

    lines 1–5

    uses SimpleGraph.fromRel_adj, ne_eq, ULift.up.injEq

    lemma not_p7_net_adj_iff.{u} (a b : Fin 6) :
        net_graph.{u}.Adj ⟨a⟩ ⟨b⟩ ↔ (a.val, b.val) ∈ ([(0, 3), (3, 0), (0, 4), (4, 0), (0, 5), (5, 0),
          (1, 4), (4, 1), (2, 5), (5, 2), (4, 5), (5, 4)] : List (ℕ × ℕ)) := by
      simp only [net_graph, SimpleGraph.fromRel_adj, ne_eq, ULift.up.injEq]
      fin_cases a <;> fin_cases b <;> decide
  2. Every vertex in the net graph is reachable from vertex 0.

    We case-split on the vertex x in Fin 6. Vertex 0 is trivially reachable from 0. Vertices 3, 4, and 5 are immediate neighbors of 0. Vertex 1 is reachable via the path 0 to 4 to 1, and vertex 2 is reachable via 0 to 5 to 2. In each case, reachability follows by transitivity along edges verified with not_p7_net_adj_iff.

    lines 7–18

    uses not_p7_net_adj_iff

    lemma not_p7_net_reachable.{u} (x : ULift.{u} (Fin 6)) : net_graph.Reachable ⟨0⟩ x := by
      obtain ⟨x⟩ := x
      have a : ∀ p q : Fin 6, net_graph.{u}.Adj ⟨p⟩ ⟨q⟩ → net_graph.{u}.Reachable ⟨p⟩ ⟨q⟩ :=
        fun p q h => h.reachable
      fin_cases x
      · rfl
      · exact (a 0 4 (by rw [not_p7_net_adj_iff]; decide)).trans (a 4 1 (by rw [not_p7_net_adj_iff]; decide))
      · exact (a 0 5 (by rw [not_p7_net_adj_iff]; decide)).trans (a 5 2 (by rw [not_p7_net_adj_iff]; decide))
      · exact a 0 3 (by rw [not_p7_net_adj_iff]; decide)
      · exact a 0 4 (by rw [not_p7_net_adj_iff]; decide)
      · exact a 0 5 (by rw [not_p7_net_adj_iff]; decide)
    
  3. Assume for contradiction that every connected, P_7-free, claw-free graph with no induced cycle of length at least 6 possesses a dominating pair.

    We introduce the universal statement as hypothesis H to derive a contradiction by exhibiting the net graph as a counterexample.

    line 22

      intro H
  4. The net graph is connected.

    The vertex set is nonempty (containing vertex 0). By not_p7_net_reachable, every vertex is reachable from 0; by symmetry and transitivity of reachability, any two vertices are connected. Thus the net graph is connected by SimpleGraph.Connected.mk.

    lines 23–26

    uses SimpleGraph.Connected.mk, not_p7_net_reachable

      have hconn : net_graph.{u_1}.Connected := by
        have : Nonempty (ULift.{u_1} (Fin 6)) := ⟨⟨0⟩⟩
        exact SimpleGraph.Connected.mk
          (fun x y => (not_p7_net_reachable x).symm.trans (not_p7_net_reachable y))
  5. The net graph is P_7-free. automation

    The net graph has 6 vertices. Since 6 < 7, is_pk_free_of_card_lt directly guarantees that it contains no induced path P_7.

    line 27

    uses is_pk_free_of_card_lt

      have hp : IsPkFree net_graph.{u_1} 7 := is_pk_free_of_card_lt _ 7 (by simp)
  6. The net graph is claw-free (contains no induced K_{1,3}). automation

    Suppose an induced embedding f of K_{1,3} into the net graph exists. Exhaustive case checking over all vertices and triples of neighbors shows that no vertex in the net graph has three mutually non-adjacent neighbors. But the center of the claw is adjacent to all three leaves, which must be distinct and mutually non-adjacent in an induced claw, producing a contradiction in every branch.

    lines 28–48

    uses not_p7_net_adj_iff, Sum.inr_injective, ULift.ext

      have hclaw : IsClawFree net_graph.{u_1} := by
        rintro ⟨f⟩
        have key : ∀ v a b c : Fin 6,
            net_graph.{u_1}.Adj ⟨v⟩ ⟨a⟩ → net_graph.{u_1}.Adj ⟨v⟩ ⟨b⟩ → net_graph.{u_1}.Adj ⟨v⟩ ⟨c⟩ →
            a ≠ b → a ≠ c → b ≠ c →
            net_graph.{u_1}.Adj ⟨a⟩ ⟨b⟩ ∨ net_graph.{u_1}.Adj ⟨a⟩ ⟨c⟩ ∨ net_graph.{u_1}.Adj ⟨b⟩ ⟨c⟩ := by
          simp only [not_p7_net_adj_iff]
          set_option synthInstance.maxSize 8192 in decide
        have hadj : ∀ i : Fin 3, net_graph.{u_1}.Adj (f (Sum.inl 0)) (f (Sum.inr i)) := fun i =>
          f.map_rel_iff.mpr (by simp)
        have hnadj : ∀ i j : Fin 3, ¬ net_graph.{u_1}.Adj (f (Sum.inr i)) (f (Sum.inr j)) := fun i j h =>
          by have := f.map_rel_iff.mp h; simp at this
        have hne : ∀ i j : Fin 3, i ≠ j → (f (Sum.inr i)).down ≠ (f (Sum.inr j)).down := by
          intro i j hij h
          exact hij (Sum.inr_injective (f.injective (ULift.ext _ _ h)))
        have := key (f (Sum.inl 0)).down (f (Sum.inr 0)).down (f (Sum.inr 1)).down (f (Sum.inr 2)).down
          (hadj 0) (hadj 1) (hadj 2) (hne 0 1 (by decide)) (hne 0 2 (by decide)) (hne 1 2 (by decide))
        rcases this with h | h | h
        · exact hnadj 0 1 h
        · exact hnadj 0 2 h
        · exact hnadj 1 2 h
  7. The net graph contains no induced cycle C_m for any m ≥ 6. automation

    Suppose f is an induced embedding of C_m into the net graph. By injectivity, m ≤ 6, which with m ≥ 6 forces m = 6. Since the vertex set has size 6, f is a bijection, so leaf 1 must be the image of some vertex i in C_6. In C_6, vertex i is adjacent to i + 1 and i - 1, which are distinct. Since f preserves adjacency, both f(i + 1) and f(i - 1) must be neighbors of vertex 1 in the net graph. But the unique neighbor of 1 is 4, forcing f(i + 1) = f(i - 1) = 4, which contradicts the injectivity of f.

    lines 49–73

    uses Fintype.card_le_of_injective, Fintype.card_fin, Fintype.card_ulift, Finite.injective_iff_surjective, SimpleGraph.cycleGraph_adj, not_p7_net_adj_iff, ULift.ext

      have hhole : ∀ m ≥ 6, IsEmpty (SimpleGraph.cycleGraph m ↪g net_graph.{u_1}) := by
        intro m hm
        refine ⟨fun f => ?_⟩
        have hcard := Fintype.card_le_of_injective f f.injective
        simp only [Fintype.card_fin, Fintype.card_ulift] at hcard
        obtain rfl : m = 6 := by omega
        have hinj : Function.Injective (fun i => (f i).down) := fun i j h =>
          f.injective (ULift.ext _ _ h)
        have hsurj := (Finite.injective_iff_surjective).mp hinj
        obtain ⟨i, hi⟩ := hsurj 1
        have h1 : (SimpleGraph.cycleGraph 6).Adj i (i + 1) := by
          rw [SimpleGraph.cycleGraph_adj]; right; simp
        have h2 : (SimpleGraph.cycleGraph 6).Adj i (i - 1) := by
          rw [SimpleGraph.cycleGraph_adj]; left; simp
        have e1 := f.map_rel_iff.mpr h1
        have e2 := f.map_rel_iff.mpr h2
        have k1 : ∀ y : Fin 6, net_graph.{u_1}.Adj ⟨1⟩ ⟨y⟩ → y = 4 := by
          simp only [not_p7_net_adj_iff]; decide
        have hfi : f i = ⟨1⟩ := ULift.ext _ _ hi
        rw [hfi] at e1 e2
        have q1 := k1 (f (i + 1)).down e1
        have q2 := k1 (f (i - 1)).down e2
        have : i + 1 = i - 1 := hinj (q1.trans q2.symm)
        have hne : ∀ j : Fin 6, j + 1 ≠ j - 1 := by decide
        exact hne i this
  8. No pair of vertices dominates the net graph, contradicting H. automation

    Applying hypothesis H to the net graph yields a purported dominating pair {u, v}. However, exhaustive checking over all pairs in Fin 6 verifies that every pair leaves at least one vertex w undominated (w is neither in {u, v} nor adjacent to either). Evaluating the dominating pair property on this w yields a contradiction in each case.

    lines 74–83

    uses not_p7_net_adj_iff, Or.inl, Or.inr

      obtain ⟨⟨u⟩, ⟨v⟩, h⟩ := H net_graph.{u_1} hconn hp hclaw hhole
      have key : ∀ u v : Fin 6, ∃ w : Fin 6, ¬ (w = u ∨ w = v ∨ net_graph.{u_1}.Adj ⟨u⟩ ⟨w⟩ ∨
          net_graph.{u_1}.Adj ⟨v⟩ ⟨w⟩) := by
        simp only [not_p7_net_adj_iff]; decide
      obtain ⟨w, hw⟩ := key u v
      rcases h ⟨w⟩ with h | h | h | h
      · exact hw (Or.inl (by simpa using h))
      · exact hw (Or.inr (Or.inl (by simpa using h)))
      · exact hw (Or.inr (Or.inr (Or.inl h)))
      · exact hw (Or.inr (Or.inr (Or.inr h)))
SimpleGraph.fromRel_adj
In a graph defined from a binary relation, two distinct vertices are adjacent if and only if the relation holds between them in at least one direction.
ne_eq
The inequality a ≠ b is defined as the negation ¬(a = b).
ULift.up.injEq
Two lifted values are equal if and only if their underlying values are equal.
not_p7_net_adj_iff
Two vertices in the net graph are adjacent if and only if their indices appear in the explicit list of twelve directed edges.
not_p7_net_reachable
Every vertex in the net graph is reachable by a walk from vertex 0.
SimpleGraph.Connected.mk
A graph is connected if its vertex set is nonempty and every pair of vertices is connected by a walk.
is_pk_free_of_card_lt
Any graph with strictly fewer than k vertices cannot contain an induced path on k vertices.
Sum.inr_injective
The second inclusion map into a sum type is injective.
ULift.ext
Two lifted elements are equal if their underlying values are equal.
Fintype.card_le_of_injective
An injective map between finite types implies that the cardinality of the domain is at most that of the codomain.
Fintype.card_fin
The finite type Fin n has cardinality n.
Fintype.card_ulift
Lifting a finite type to another universe preserves its cardinality.
Finite.injective_iff_surjective
A self-map on a finite set is injective if and only if it is surjective.
SimpleGraph.cycleGraph_adj
In a cycle graph on n + 2 vertices, two vertices are adjacent if and only if their cyclic difference is 1 or -1.
Or.inl
Infers a disjunction given a proof of its left disjunct.
Or.inr
Infers a disjunction given a proof of its right disjunct.

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

lemma not_p7_net_adj_iff.{u} (a b : Fin 6) :    net_graph.{u}.Adj ⟨a⟩ ⟨b⟩ ↔ (a.val, b.val) ∈ ([(0, 3), (3, 0), (0, 4), (4, 0), (0, 5), (5, 0),      (1, 4), (4, 1), (2, 5), (5, 2), (4, 5), (5, 4)] : List (ℕ × ℕ)) := by  simp only [net_graph, SimpleGraph.fromRel_adj, ne_eq, ULift.up.injEq]  fin_cases a <;> fin_cases b <;> decidelemma not_p7_net_reachable.{u} (x : ULift.{u} (Fin 6)) : net_graph.Reachable ⟨0⟩ x := by  obtain ⟨x⟩ := x  have a : ∀ p q : Fin 6, net_graph.{u}.Adj ⟨p⟩ ⟨q⟩ → net_graph.{u}.Reachable ⟨p⟩ ⟨q⟩ :=    fun p q h => h.reachable  fin_cases x  · rfl  · exact (a 0 4 (by rw [not_p7_net_adj_iff]; decide)).trans (a 4 1 (by rw [not_p7_net_adj_iff]; decide))  · exact (a 0 5 (by rw [not_p7_net_adj_iff]; decide)).trans (a 5 2 (by rw [not_p7_net_adj_iff]; decide))  · exact a 0 3 (by rw [not_p7_net_adj_iff]; decide)  · exact a 0 4 (by rw [not_p7_net_adj_iff]; decide)  · exact a 0 5 (by rw [not_p7_net_adj_iff]; decide)theorem not_p7_claw_free_dominating_pair_of_no_hole : ¬ (∀ {V : Type*} [Fintype V] (G : SimpleGraph V)    (hconn : G.Connected) (hp : IsPkFree G 7) (hclaw : IsClawFree G)    (hno_hole : ∀ m ≥ 6, IsEmpty (SimpleGraph.cycleGraph m ↪g G)), ∃ u v : V, ∀ w : V, w = u ∨ w = v ∨ G.Adj u w ∨ G.Adj v w) := by  intro H  have hconn : net_graph.{u_1}.Connected := by    have : Nonempty (ULift.{u_1} (Fin 6)) := ⟨⟨0⟩⟩    exact SimpleGraph.Connected.mk      (fun x y => (not_p7_net_reachable x).symm.trans (not_p7_net_reachable y))  have hp : IsPkFree net_graph.{u_1} 7 := is_pk_free_of_card_lt _ 7 (by simp)  have hclaw : IsClawFree net_graph.{u_1} := by    rintro ⟨f⟩    have key : ∀ v a b c : Fin 6,        net_graph.{u_1}.Adj ⟨v⟩ ⟨a⟩ → net_graph.{u_1}.Adj ⟨v⟩ ⟨b⟩ → net_graph.{u_1}.Adj ⟨v⟩ ⟨c⟩ →        a ≠ b → a ≠ c → b ≠ c →        net_graph.{u_1}.Adj ⟨a⟩ ⟨b⟩ ∨ net_graph.{u_1}.Adj ⟨a⟩ ⟨c⟩ ∨ net_graph.{u_1}.Adj ⟨b⟩ ⟨c⟩ := by      simp only [not_p7_net_adj_iff]      set_option synthInstance.maxSize 8192 in decide    have hadj : ∀ i : Fin 3, net_graph.{u_1}.Adj (f (Sum.inl 0)) (f (Sum.inr i)) := fun i =>      f.map_rel_iff.mpr (by simp)    have hnadj : ∀ i j : Fin 3, ¬ net_graph.{u_1}.Adj (f (Sum.inr i)) (f (Sum.inr j)) := fun i j h =>      by have := f.map_rel_iff.mp h; simp at this    have hne : ∀ i j : Fin 3, i ≠ j → (f (Sum.inr i)).down ≠ (f (Sum.inr j)).down := by      intro i j hij h      exact hij (Sum.inr_injective (f.injective (ULift.ext _ _ h)))    have := key (f (Sum.inl 0)).down (f (Sum.inr 0)).down (f (Sum.inr 1)).down (f (Sum.inr 2)).down      (hadj 0) (hadj 1) (hadj 2) (hne 0 1 (by decide)) (hne 0 2 (by decide)) (hne 1 2 (by decide))    rcases this with h | h | h    · exact hnadj 0 1 h    · exact hnadj 0 2 h    · exact hnadj 1 2 h  have hhole : ∀ m ≥ 6, IsEmpty (SimpleGraph.cycleGraph m ↪g net_graph.{u_1}) := by    intro m hm    refine ⟨fun f => ?_⟩    have hcard := Fintype.card_le_of_injective f f.injective    simp only [Fintype.card_fin, Fintype.card_ulift] at hcard    obtain rfl : m = 6 := by omega    have hinj : Function.Injective (fun i => (f i).down) := fun i j h =>      f.injective (ULift.ext _ _ h)    have hsurj := (Finite.injective_iff_surjective).mp hinj    obtain ⟨i, hi⟩ := hsurj 1    have h1 : (SimpleGraph.cycleGraph 6).Adj i (i + 1) := by      rw [SimpleGraph.cycleGraph_adj]; right; simp    have h2 : (SimpleGraph.cycleGraph 6).Adj i (i - 1) := by      rw [SimpleGraph.cycleGraph_adj]; left; simp    have e1 := f.map_rel_iff.mpr h1    have e2 := f.map_rel_iff.mpr h2    have k1 : ∀ y : Fin 6, net_graph.{u_1}.Adj ⟨1⟩ ⟨y⟩ → y = 4 := by      simp only [not_p7_net_adj_iff]; decide    have hfi : f i = ⟨1⟩ := ULift.ext _ _ hi    rw [hfi] at e1 e2    have q1 := k1 (f (i + 1)).down e1    have q2 := k1 (f (i - 1)).down e2    have : i + 1 = i - 1 := hinj (q1.trans q2.symm)    have hne : ∀ j : Fin 6, j + 1 ≠ j - 1 := by decide    exact hne i this  obtain ⟨⟨u⟩, ⟨v⟩, h⟩ := H net_graph.{u_1} hconn hp hclaw hhole  have key : ∀ u v : Fin 6, ∃ w : Fin 6, ¬ (w = u ∨ w = v ∨ net_graph.{u_1}.Adj ⟨u⟩ ⟨w⟩ ∨      net_graph.{u_1}.Adj ⟨v⟩ ⟨w⟩) := by    simp only [not_p7_net_adj_iff]; decide  obtain ⟨w, hw⟩ := key u v  rcases h ⟨w⟩ with h | h | h | h  · exact hw (Or.inl (by simpa using h))  · exact hw (Or.inr (Or.inl (by simpa using h)))  · exact hw (Or.inr (Or.inr (Or.inl h)))  · exact hw (Or.inr (Or.inr (Or.inr h)))
See it in the graphDiscuss this resultChallenge it