not_p7_claw_free_dominating_pair_of_no_hole
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.
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.
uses
SimpleGraph.fromRel_adj,ne_eq,ULift.up.injEqlemma 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
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.
uses
not_p7_net_adj_ifflemma 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)
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.
intro HThe 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.
uses
SimpleGraph.Connected.mk,not_p7_net_reachablehave 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))
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.
uses
is_pk_free_of_card_lthave hp : IsPkFree net_graph.{u_1} 7 := is_pk_free_of_card_lt _ 7 (by simp)
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.
uses
not_p7_net_adj_iff,Sum.inr_injective,ULift.exthave 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
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.
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.exthave 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
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.
uses
not_p7_net_adj_iff,Or.inl,Or.inrobtain ⟨⟨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.
- The net graph's vertex set Fin 6 is universe-lifted to ULift (Fin 6) to accommodate the polymorphic universe of the theorem.
- Finite graph properties (explicit adjacency list, claw-freeness, and the non-existence of a dominating pair) are settled by the decide tactic, which performs exhaustive computation over the finite type Fin 6.
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.
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)))