AFTD Auto-Formalizing Theoretical Domains

odd_cycle_is_claw_free

theoremverified

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.

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

    lines 4–8

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

    lines 9–23

    uses SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj

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

    lines 24–35

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

    lines 36–45

    uses Finset.card_insert_of_notMem, Finset.card_singleton, Finset.mem_singleton, Finset.mem_insert

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

    lines 46–52

    uses Finset.mem_insert, Finset.mem_singleton

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

    lines 53–57

    uses Finset.card_le_card, SimpleGraph.degree

      have hle := Finset.card_le_card hsub
      rw [hcard] at hle
      have hdeg_v := hdeg v
      rw [← SimpleGraph.degree] at hle
      omega
  7. 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.

    lines 62–63

    uses odd_cycle_is_claw_free_of_degree_le_two

      apply odd_cycle_is_claw_free_of_degree_le_two
      intro v
  8. 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.

    lines 64–68

    uses SimpleGraph.cycleGraph_degree_three_le

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

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

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