odd_cycle_is_claw_free
For every integer n ≥ 1, the odd cycle graph C_{2n+1} is claw-free.
Statement
theorem odd_cycle_is_claw_free (n : ℕ) (hn : 1 ≤ n) :
IsClawFree (SimpleGraph.cycleGraph (2 * n + 1))- Source
- arXiv:2611.09072 Claw-free minimal factor-critical and bicritical graphs, proof of Theorem 1.4
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- IsClawFreeA simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
Read back from the Lean
For every natural number $n$ such that $1 \le n$, the cycle graph on $2n + 1$ vertices (SimpleGraph.cycleGraph (2 * n + 1)) is claw-free (does not contain the complete bipartite graph $K_{1, 3}$ as an induced subgraph).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof first establishes a general lemma: any graph with maximum degree at most 2 is claw-free. An induced claw K_{1,3} requires a central vertex with three distinct, pairwise non-adjacent neighbors, forcing its degree to be at least 3 and contradicting the maximum degree bound. The main theorem then deduces that the odd cycle C_{2n+1} (n ≥ 1) is claw-free because every cycle of length at least 3 is 2-regular.
Assume for contradiction that G contains an induced claw K_{1,3}, and identify its center v and its three leaves a, b, c.
The definition of claw-freeness asserts that there is no induced subgraph embedding of K_{1,3} into G. We assume for contradiction that such an embedding f exists. We define v to be the image of the center vertex (the unique element of Fin 1) and a, b, c to be the images of the three independent vertices (the elements 0, 1, 2 of Fin 3).
rintro ⟨f⟩ set v : V := f (Sum.inl 0) set a : V := f (Sum.inr 0) set b : V := f (Sum.inr 1) set c : V := f (Sum.inr 2)
The vertices a, b, and c are all neighbors of v in G.
In the complete bipartite graph K_{1,3}, the center vertex is adjacent to each of the three leaves by definition (completeBipartiteGraph_adj). Because f is an induced graph embedding, it preserves adjacency. Translating adjacency to membership in the neighbor finset (SimpleGraph.mem_neighborFinset), each of a, b, and c belongs to the neighbor finset of v.
uses
SimpleGraph.mem_neighborFinset,completeBipartiteGraph_adjhave ha : a ∈ G.neighborFinset v := by rw [SimpleGraph.mem_neighborFinset] have hadj : (completeBipartiteGraph (Fin 1) (Fin 3)).Adj (Sum.inl 0) (Sum.inr 0) := by simp [completeBipartiteGraph_adj] exact f.map_rel_iff.mpr hadj have hb : b ∈ G.neighborFinset v := by rw [SimpleGraph.mem_neighborFinset] have hadj : (completeBipartiteGraph (Fin 1) (Fin 3)).Adj (Sum.inl 0) (Sum.inr 1) := by simp [completeBipartiteGraph_adj] exact f.map_rel_iff.mpr hadj have hc : c ∈ G.neighborFinset v := by rw [SimpleGraph.mem_neighborFinset] have hadj : (completeBipartiteGraph (Fin 1) (Fin 3)).Adj (Sum.inl 0) (Sum.inr 2) := by simp [completeBipartiteGraph_adj] exact f.map_rel_iff.mpr hadj
The vertices a, b, and c are pairwise distinct.
Because f is an embedding, its underlying vertex map is injective. If any two of a, b, c were equal, injectivity would force two distinct indices among 0, 1, 2 in Fin 3 to be equal, which is a contradiction. Hence a ≠ b, b ≠ c, and a ≠ c.
have hab : a ≠ b := by intro h have := f.injective h contradiction have hbc : b ≠ c := by intro h have := f.injective h contradiction have hac : a ≠ c := by intro h have := f.injective h contradiction
The finite set {a, b, c} has cardinality 3.
Since b ≠ c, b ∉ {c} (by Finset.mem_singleton), and since a ≠ b and a ≠ c, a ∉ {b, c} (by Finset.mem_insert and Finset.mem_singleton). Applying Finset.card_insert_of_notMem twice and Finset.card_singleton shows that |{a, b, c}| = 3.
uses
Finset.card_insert_of_notMem,Finset.card_singleton,Finset.mem_singleton,Finset.mem_inserthave hcard : ({a, b, c} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · intro h simp only [Finset.mem_singleton] at h exact hbc h · intro h simp only [Finset.mem_insert, Finset.mem_singleton] at h rcases h with h | h · exact hab h · exact hac h
The set {a, b, c} is a subset of the neighbor set of v.
Any element x ∈ {a, b, c} must be equal to a, b, or c (Finset.mem_insert, Finset.mem_singleton). Since each was shown to be a neighbor of v, every element of {a, b, c} belongs to the neighbor finset of v.
uses
Finset.mem_insert,Finset.mem_singletonhave hsub : ({a, b, c} : Finset V) ⊆ G.neighborFinset v := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact ha · exact hb · exact hc
Contradiction: v has at least 3 neighbors, but every vertex has degree at most 2. automation
Monotonicity of cardinality under subset inclusion (Finset.card_le_card) yields 3 ≤ |N(v)|. Rewriting the cardinality of the neighbor finset as the vertex degree (SimpleGraph.degree), we have 3 ≤ deg(v). Combining this with the assumption hdeg that deg(v) ≤ 2, integer linear arithmetic (omega) derives False.
uses
Finset.card_le_card,SimpleGraph.degreehave hle := Finset.card_le_card hsub rw [hcard] at hle have hdeg_v := hdeg v rw [← SimpleGraph.degree] at hle omega
To show that the odd cycle C_{2n+1} is claw-free, it suffices to show that every vertex has degree at most 2.
We apply the helper theorem odd_cycle_is_claw_free_of_degree_le_two to the cycle graph C_{2n+1}, which reduces the goal to proving that deg(v) ≤ 2 for an arbitrary vertex v.
uses
odd_cycle_is_claw_free_of_degree_le_twoapply odd_cycle_is_claw_free_of_degree_le_two intro v
Every vertex in the cycle graph C_{2n+1} has degree 2 when n ≥ 1, completing the proof.
We split into cases on n. The case n = 0 is ruled out by the hypothesis 1 ≤ n. When n = k + 1, the cycle has length 2(k + 1) + 1 = 2k + 3 ≥ 3, so SimpleGraph.cycleGraph_degree_three_le states that every vertex has degree exactly 2. Thus deg(v) ≤ 2 holds.
uses
SimpleGraph.cycleGraph_degree_three_lercases n with _ | k · omega · have h : (SimpleGraph.cycleGraph (2 * (k + 1) + 1)).degree v = 2 := SimpleGraph.cycleGraph_degree_three_le omega
completeBipartiteGraph_adj- In a complete bipartite graph, two vertices are adjacent if and only if one belongs to the first partition and the other belongs to the second.
SimpleGraph.mem_neighborFinset- A vertex w is in the neighbor finset of v if and only if v and w are adjacent in the graph.
Finset.card_insert_of_notMem- Inserting an element into a finite set increases its cardinality by 1, provided the element was not already in the set.
Finset.card_singleton- A singleton set has cardinality 1.
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it equals a.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the cardinality of the other.
SimpleGraph.degree- The degree of a vertex in a simple graph is defined as the cardinality of its neighbor finset.
odd_cycle_is_claw_free_of_degree_le_two- A finite simple graph in which every vertex has degree at most 2 is claw-free.
SimpleGraph.cycleGraph_degree_three_le- Every vertex in a cycle graph with at least 3 vertices has degree 2.
- In Lean, claw-freeness of a graph G is defined as the negation of an induced subgraph embedding from the complete bipartite graph K_{1,3} into G. The `rintro ⟨f⟩` tactic extracts this embedding to set up the contradiction.
- The `omega` tactic discharges linear integer arithmetic goals: deriving False from 3 ≤ deg(v) and deg(v) ≤ 2 in step 6, and ruling out the impossible case n = 0 given 1 ≤ n in step 8.
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.
theorem odd_cycle_is_claw_free_of_degree_le_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hdeg : ∀ v : V, G.degree v ≤ 2) : IsClawFree G := by rintro ⟨f⟩ set v : V := f (Sum.inl 0) set a : V := f (Sum.inr 0) set b : V := f (Sum.inr 1) set c : V := f (Sum.inr 2) have ha : a ∈ G.neighborFinset v := by rw [SimpleGraph.mem_neighborFinset] have hadj : (completeBipartiteGraph (Fin 1) (Fin 3)).Adj (Sum.inl 0) (Sum.inr 0) := by simp [completeBipartiteGraph_adj] exact f.map_rel_iff.mpr hadj have hb : b ∈ G.neighborFinset v := by rw [SimpleGraph.mem_neighborFinset] have hadj : (completeBipartiteGraph (Fin 1) (Fin 3)).Adj (Sum.inl 0) (Sum.inr 1) := by simp [completeBipartiteGraph_adj] exact f.map_rel_iff.mpr hadj have hc : c ∈ G.neighborFinset v := by rw [SimpleGraph.mem_neighborFinset] have hadj : (completeBipartiteGraph (Fin 1) (Fin 3)).Adj (Sum.inl 0) (Sum.inr 2) := by simp [completeBipartiteGraph_adj] exact f.map_rel_iff.mpr hadj have hab : a ≠ b := by intro h have := f.injective h contradiction have hbc : b ≠ c := by intro h have := f.injective h contradiction have hac : a ≠ c := by intro h have := f.injective h contradiction have hcard : ({a, b, c} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · intro h simp only [Finset.mem_singleton] at h exact hbc h · intro h simp only [Finset.mem_insert, Finset.mem_singleton] at h rcases h with h | h · exact hab h · exact hac h have hsub : ({a, b, c} : Finset V) ⊆ G.neighborFinset v := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact ha · exact hb · exact hc have hle := Finset.card_le_card hsub rw [hcard] at hle have hdeg_v := hdeg v rw [← SimpleGraph.degree] at hle omega/-- The odd cycle graph C_{2n+1} is claw-free for any n ≥ 1. -/theorem odd_cycle_is_claw_free (n : ℕ) (hn : 1 ≤ n) : IsClawFree (SimpleGraph.cycleGraph (2 * n + 1)) := by apply odd_cycle_is_claw_free_of_degree_le_two intro v rcases n with _ | k · omega · have h : (SimpleGraph.cycleGraph (2 * (k + 1) + 1)).degree v = 2 := SimpleGraph.cycleGraph_degree_three_le omega