AFTD Auto-Formalizing Theoretical Domains

odd_cycle_is_minimal_factor_critical

theoremverified

For every integer n ≥ 1, the odd cycle graph C_{2n+1} is minimal factor-critical.

Statement

theorem odd_cycle_is_minimal_factor_critical (n : ℕ) (hn : 1 ≤ n) :
    IsMinimalFactorCritical (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 3
  • IsFactorCriticalA simple graph G on a vertex type V is factor-critical if for every vertex v : V, the induced subgraph of G on {v}ᶜ has a perfect…
  • odd_cycle_is_factor_criticalFor every integer n ≥ 1, the odd cycle graph C_{2n+1} is factor-critical.
  • IsMinimalFactorCriticalA simple graph G on a vertex type V is minimal factor-critical if G is factor-critical and for every edge e ∈ G.edgeSet, the graph…

Read back from the Lean

For every natural number $n$ such that $1 \le n$, the cycle graph on $2n + 1$ vertices is minimal factor-critical (meaning it is factor-critical, and deleting any of its edges yields a graph that is not factor-critical).

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

A graph is minimal factor-critical if it is factor-critical and deleting any edge leaves a graph that is not factor-critical. The odd cycle C_{2n+1} is already known to be factor-critical. In C_{2n+1}, every vertex has degree 2, so deleting any edge reduces the degree of its endpoints to 1; removing the unique remaining neighbor of such an endpoint leaves that endpoint isolated, so the remaining graph cannot have a perfect matching.

  1. If two vertices u and v are adjacent in C_{2n+1}, then v = u - 1 or v = u + 1.

    By definition of the cycle graph, u and v are adjacent if and only if the value of u - v or v - u in Fin (2n+1) is 1. Since 1 in Fin (2n+1) has value 1 by odd_cycle_is_factor_critical_one_val, Fin.ext equates u - v = 1 (hence v = u - 1) or v - u = 1 (hence v = u + 1).

    lines 3–19

    uses SimpleGraph.cycleGraph_adj', Fin.ext, odd_cycle_is_factor_critical_one_val

      rw [SimpleGraph.cycleGraph_adj']
      constructor
      · rintro (h | h)
        · left
          have : u - v = 1 := by
            apply Fin.ext
            rw [h]
            exact (odd_cycle_is_factor_critical_one_val hn).symm
          rw [← this]
          abel
        · right
          have : v - u = 1 := by
            apply Fin.ext
            rw [h]
            exact (odd_cycle_is_factor_critical_one_val hn).symm
          rw [← this]
          abel
  2. If v = u - 1 or v = u + 1 in Fin (2n+1), then u and v are adjacent in C_{2n+1}.

    If v = u - 1, then u - v = 1, which has integer value 1 by odd_cycle_is_factor_critical_one_val; if v = u + 1, then v - u = 1, which likewise has value 1. In either case, the adjacency condition for the cycle graph is satisfied.

    lines 20–28

    uses odd_cycle_is_factor_critical_one_val

      · rintro (rfl | rfl)
        · left
          have : u - (u - 1) = 1 := by abel
          rw [this]
          exact odd_cycle_is_factor_critical_one_val hn
        · right
          have : u + 1 - u = 1 := by abel
          rw [this]
          exact odd_cycle_is_factor_critical_one_val hn
  3. No vertex u in C_{2n+1} satisfies u = u - 1.

    If u = u - 1, subtracting gives 1 = u - (u - 1) = u - u = 0 by sub_self. Taking the integer value via congrArg gives 1 = 0 by odd_cycle_is_factor_critical_one_val, which is impossible.

    lines 31–37

    uses sub_self, congrArg, odd_cycle_is_factor_critical_one_val

      intro h
      have h1 : (1 : Fin (2 * n + 1)) = 0 := by
        have : u - (u - 1) = 1 := by abel
        rw [← this, ← h, sub_self]
      have h2 := congrArg Fin.val h1
      rw [odd_cycle_is_factor_critical_one_val hn] at h2
      cases h2
  4. No vertex u in C_{2n+1} satisfies u = u + 1.

    If u = u + 1, subtracting gives 1 = (u + 1) - u = u - u = 0 by sub_self. Taking the integer value via congrArg gives 1 = 0 by odd_cycle_is_factor_critical_one_val, a contradiction.

    lines 40–46

    uses sub_self, congrArg, odd_cycle_is_factor_critical_one_val

      intro h
      have h1 : (1 : Fin (2 * n + 1)) = 0 := by
        have : (u + 1) - u = 1 := by abel
        rw [← this, ← h, sub_self]
      have h2 := congrArg Fin.val h1
      rw [odd_cycle_is_factor_critical_one_val hn] at h2
      cases h2
  5. C_{2n+1} is factor-critical, and any edge e has the form {x, x - 1} or {x, x + 1}.

    C_{2n+1} is factor-critical by odd_cycle_is_factor_critical. Minimality requires that deleting any edge e leaves a graph that is not factor-critical. Representing e as an unordered pair s(x, y) via Sym2.inductionOn, edge membership implies x and y are adjacent by SimpleGraph.mem_edgeSet, so y = x - 1 or y = x + 1 by odd_cycle_is_minimal_factor_critical_adj_iff.

    lines 51–57

    uses odd_cycle_is_factor_critical, Sym2.inductionOn, SimpleGraph.mem_edgeSet, odd_cycle_is_minimal_factor_critical_adj_iff

      refine ⟨odd_cycle_is_factor_critical n hn, ?_⟩
      intro e he
      induction e using Sym2.inductionOn with
      | hf x y =>
        rw [SimpleGraph.mem_edgeSet] at he
        have hy : y = x - 1 ∨ y = x + 1 := (odd_cycle_is_minimal_factor_critical_adj_iff n hn x y).mp he
        rcases hy with rfl | rfl
  6. In C_{2n+1} \ {{x, x - 1}}, vertex x is distinct from x + 1 and has x + 1 as its only neighbor.

    Assume for contradiction that deleting {x, x - 1} preserves factor-criticality. By odd_cycle_is_minimal_factor_critical_ne_add_one, x ≠ x + 1. Any neighbor w of x in the edge-deleted graph must be a neighbor in C_{2n+1} with {x, w} ≠ {x, x - 1} by SimpleGraph.deleteEdges_adj. Since the only neighbors in C_{2n+1} are x - 1 and x + 1 (by odd_cycle_is_minimal_factor_critical_adj_iff), and w = x - 1 is excluded by Set.mem_singleton, w must be x + 1.

    lines 58–68

    uses odd_cycle_is_minimal_factor_critical_ne_add_one, SimpleGraph.deleteEdges_adj, odd_cycle_is_minimal_factor_critical_adj_iff, Set.mem_singleton

        · intro hFC
          have huv : x ≠ x + 1 := odd_cycle_is_minimal_factor_critical_ne_add_one n hn x
          have h_iso : ∀ w, (SimpleGraph.deleteEdges (SimpleGraph.cycleGraph (2 * n + 1)) {s(x, x - 1)}).Adj x w → w = x + 1 := by
            intro w hw
            rw [SimpleGraph.deleteEdges_adj] at hw
            have hw_adj := (odd_cycle_is_minimal_factor_critical_adj_iff n hn x w).mp hw.1
            rcases hw_adj with rfl | rfl
            · exfalso
              apply hw.2
              exact Set.mem_singleton _
            · rfl
  7. Deleting the edge {x, x - 1} destroys factor-criticality.

    If C_{2n+1} \ {{x, x - 1}} were factor-critical, removing vertex x + 1 would leave a graph with a perfect matching M by SimpleGraph.Subgraph.isPerfectMatching_iff. Since x ≠ x + 1, vertex x must be matched in M to some vertex w distinct from x + 1. By SimpleGraph.induce_adj, w must be adjacent to x in C_{2n+1} \ {{x, x - 1}}. But the previous step showed x + 1 is the unique neighbor of x in this graph, forcing w = x + 1, which contradicts w ≠ x + 1.

    lines 69–76

    uses SimpleGraph.Subgraph.isPerfectMatching_iff, SimpleGraph.induce_adj

          have h_ex := hFC (x + 1)
          obtain ⟨M, hM⟩ := h_ex
          rw [SimpleGraph.Subgraph.isPerfectMatching_iff] at hM
          obtain ⟨w, hw, -⟩ := hM ⟨x, huv⟩
          have hadj := M.adj_sub hw
          rw [SimpleGraph.induce_adj] at hadj
          have hw_eq := h_iso w.1 hadj
          exact w.2 (by simp [hw_eq])
  8. In C_{2n+1} \ {{x, x + 1}}, vertex x is distinct from x - 1 and has x - 1 as its only neighbor.

    Assume for contradiction that deleting {x, x + 1} preserves factor-criticality. By odd_cycle_is_minimal_factor_critical_ne_sub_one, x ≠ x - 1. Any neighbor w of x in the edge-deleted graph must be adjacent to x in C_{2n+1} without {x, w} = {x, x + 1} by SimpleGraph.deleteEdges_adj. By odd_cycle_is_minimal_factor_critical_adj_iff, w must be x - 1 or x + 1; excluding x + 1 via Set.mem_singleton leaves w = x - 1 as the sole neighbor.

    lines 77–87

    uses odd_cycle_is_minimal_factor_critical_ne_sub_one, SimpleGraph.deleteEdges_adj, odd_cycle_is_minimal_factor_critical_adj_iff, Set.mem_singleton

        · intro hFC
          have huv : x ≠ x - 1 := odd_cycle_is_minimal_factor_critical_ne_sub_one n hn x
          have h_iso : ∀ w, (SimpleGraph.deleteEdges (SimpleGraph.cycleGraph (2 * n + 1)) {s(x, x + 1)}).Adj x w → w = x - 1 := by
            intro w hw
            rw [SimpleGraph.deleteEdges_adj] at hw
            have hw_adj := (odd_cycle_is_minimal_factor_critical_adj_iff n hn x w).mp hw.1
            rcases hw_adj with rfl | rfl
            · rfl
            · exfalso
              apply hw.2
              exact Set.mem_singleton _
  9. Deleting the edge {x, x + 1} destroys factor-criticality, completing the proof that C_{2n+1} is minimal factor-critical.

    If C_{2n+1} \ {{x, x + 1}} were factor-critical, removing vertex x - 1 would leave a graph with a perfect matching M by SimpleGraph.Subgraph.isPerfectMatching_iff. Since x ≠ x - 1, vertex x must be matched to some vertex w distinct from x - 1. By SimpleGraph.induce_adj, w is adjacent to x in C_{2n+1} \ {{x, x + 1}}, which forces w = x - 1 by the previous step, a contradiction. Thus deleting any edge destroys factor-criticality.

    lines 88–95

    uses SimpleGraph.Subgraph.isPerfectMatching_iff, SimpleGraph.induce_adj

          have h_ex := hFC (x - 1)
          obtain ⟨M, hM⟩ := h_ex
          rw [SimpleGraph.Subgraph.isPerfectMatching_iff] at hM
          obtain ⟨w, hw, -⟩ := hM ⟨x, huv⟩
          have hadj := M.adj_sub hw
          rw [SimpleGraph.induce_adj] at hadj
          have hw_eq := h_iso w.1 hadj
          exact w.2 (by simp [hw_eq])
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
SimpleGraph.Subgraph.isPerfectMatching_iff
A subgraph M of G is a perfect matching if and only if every vertex of G is adjacent in M to exactly one vertex.
SimpleGraph.cycleGraph_adj'
In the cycle graph of order n, two vertices u and v are adjacent if and only if the difference u - v or v - u has integer value 1.
SimpleGraph.deleteEdges_adj
Two vertices are adjacent in an edge-deleted graph G \ s if and only if they are adjacent in G and the edge between them does not belong to s.
SimpleGraph.induce_adj
Two vertices of an induced subgraph are adjacent if and only if they are adjacent in the ambient graph.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of a graph if and only if v and w are adjacent.
Set.mem_singleton
An element a belongs to the singleton set {a}.
congrArg
Applying a function to both sides of an equality preserves the equality.
odd_cycle_is_factor_critical
For any n ≥ 1, the odd cycle graph C_{2n+1} is factor-critical.
odd_cycle_is_minimal_factor_critical_adj_iff
In the cycle graph C_{2n+1} (with n ≥ 1), vertices u and v are adjacent if and only if v = u - 1 or v = u + 1.
odd_cycle_is_minimal_factor_critical_ne_add_one
In Fin (2n+1) with n ≥ 1, no vertex u equals u + 1.
odd_cycle_is_minimal_factor_critical_ne_sub_one
In Fin (2n+1) with n ≥ 1, no vertex u equals u - 1.
odd_cycle_is_factor_critical_one_val
For n ≥ 1, the integer value of 1 in Fin (2n+1) is 1.
sub_self
In any additive group, subtracting an element from itself yields zero (a - a = 0).
Sym2.inductionOn
Every element of Sym²(α) (an unordered pair) can be expressed as s(x, y) for some x, y in α.

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_minimal_factor_critical_adj_iff (n : ℕ) (hn : 1 ≤ n) (u v : Fin (2 * n + 1)) :    (SimpleGraph.cycleGraph (2 * n + 1)).Adj u v ↔ v = u - 1 ∨ v = u + 1 := by  rw [SimpleGraph.cycleGraph_adj']  constructor  · rintro (h | h)    · left      have : u - v = 1 := by        apply Fin.ext        rw [h]        exact (odd_cycle_is_factor_critical_one_val hn).symm      rw [← this]      abel    · right      have : v - u = 1 := by        apply Fin.ext        rw [h]        exact (odd_cycle_is_factor_critical_one_val hn).symm      rw [← this]      abel  · rintro (rfl | rfl)    · left      have : u - (u - 1) = 1 := by abel      rw [this]      exact odd_cycle_is_factor_critical_one_val hn    · right      have : u + 1 - u = 1 := by abel      rw [this]      exact odd_cycle_is_factor_critical_one_val hntheorem odd_cycle_is_minimal_factor_critical_ne_sub_one (n : ℕ) (hn : 1 ≤ n) (u : Fin (2 * n + 1)) : u ≠ u - 1 := by  intro h  have h1 : (1 : Fin (2 * n + 1)) = 0 := by    have : u - (u - 1) = 1 := by abel    rw [← this, ← h, sub_self]  have h2 := congrArg Fin.val h1  rw [odd_cycle_is_factor_critical_one_val hn] at h2  cases h2theorem odd_cycle_is_minimal_factor_critical_ne_add_one (n : ℕ) (hn : 1 ≤ n) (u : Fin (2 * n + 1)) : u ≠ u + 1 := by  intro h  have h1 : (1 : Fin (2 * n + 1)) = 0 := by    have : (u + 1) - u = 1 := by abel    rw [← this, ← h, sub_self]  have h2 := congrArg Fin.val h1  rw [odd_cycle_is_factor_critical_one_val hn] at h2  cases h2/-- The odd cycle graph C_{2n+1} is minimal factor-critical for any n ≥ 1. -/theorem odd_cycle_is_minimal_factor_critical (n : ℕ) (hn : 1 ≤ n) :    IsMinimalFactorCritical (SimpleGraph.cycleGraph (2 * n + 1)) := by  refine ⟨odd_cycle_is_factor_critical n hn, ?_⟩  intro e he  induction e using Sym2.inductionOn with  | hf x y =>    rw [SimpleGraph.mem_edgeSet] at he    have hy : y = x - 1 ∨ y = x + 1 := (odd_cycle_is_minimal_factor_critical_adj_iff n hn x y).mp he    rcases hy with rfl | rfl    · intro hFC      have huv : x ≠ x + 1 := odd_cycle_is_minimal_factor_critical_ne_add_one n hn x      have h_iso : ∀ w, (SimpleGraph.deleteEdges (SimpleGraph.cycleGraph (2 * n + 1)) {s(x, x - 1)}).Adj x w → w = x + 1 := by        intro w hw        rw [SimpleGraph.deleteEdges_adj] at hw        have hw_adj := (odd_cycle_is_minimal_factor_critical_adj_iff n hn x w).mp hw.1        rcases hw_adj with rfl | rfl        · exfalso          apply hw.2          exact Set.mem_singleton _        · rfl      have h_ex := hFC (x + 1)      obtain ⟨M, hM⟩ := h_ex      rw [SimpleGraph.Subgraph.isPerfectMatching_iff] at hM      obtain ⟨w, hw, -⟩ := hM ⟨x, huv⟩      have hadj := M.adj_sub hw      rw [SimpleGraph.induce_adj] at hadj      have hw_eq := h_iso w.1 hadj      exact w.2 (by simp [hw_eq])    · intro hFC      have huv : x ≠ x - 1 := odd_cycle_is_minimal_factor_critical_ne_sub_one n hn x      have h_iso : ∀ w, (SimpleGraph.deleteEdges (SimpleGraph.cycleGraph (2 * n + 1)) {s(x, x + 1)}).Adj x w → w = x - 1 := by        intro w hw        rw [SimpleGraph.deleteEdges_adj] at hw        have hw_adj := (odd_cycle_is_minimal_factor_critical_adj_iff n hn x w).mp hw.1        rcases hw_adj with rfl | rfl        · rfl        · exfalso          apply hw.2          exact Set.mem_singleton _      have h_ex := hFC (x - 1)      obtain ⟨M, hM⟩ := h_ex      rw [SimpleGraph.Subgraph.isPerfectMatching_iff] at hM      obtain ⟨w, hw, -⟩ := hM ⟨x, huv⟩      have hadj := M.adj_sub hw      rw [SimpleGraph.induce_adj] at hadj      have hw_eq := h_iso w.1 hadj      exact w.2 (by simp [hw_eq])
See it in the graphDiscuss this resultChallenge it