AFTD Auto-Formalizing Theoretical Domains

odd_cycle_is_factor_critical

theoremverified

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

Statement

theorem odd_cycle_is_factor_critical (n : ℕ) (hn : 1 ≤ n) :
    IsFactorCritical (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
  • 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…
Used by 1

Read back from the Lean

For every natural number $n$ such that $1 \le n$, the cycle graph on $2n + 1$ vertices is factor-critical (that is, deleting any vertex leaves an induced subgraph that admits a perfect matching).

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

To prove that the odd cycle graph C_{2n+1} is factor-critical, we must show that removing any vertex v leaves a graph with a perfect matching. When v is removed, the remaining 2n vertices form an even-length path, which admits a natural pairing: in cyclic order from v, pair each odd offset with the subsequent even offset by mapping u to u + 1 if (u - v).val is odd and to u - 1 if (u - v).val is even. After verifying that this pairing never hits v, is an involution, and pairs only adjacent vertices, we define a subgraph on V(C_{2n+1}) \ {v} with these edges. Since every vertex has exactly one paired neighbor, this subgraph is a 1-regular spanning subgraph, that is, a perfect matching.

  1. The numerical value of 1 in Fin (2n + 1) is 1.

    Because n ≥ 1, the modulus 2n + 1 ≥ 3 is nonzero. The value of 1 in Fin (2n + 1) is given by 1 % (2n + 1), which simplifies to 1 because 1 < 2n + 1.

    lines 3–5

    uses Fin.val_one', Nat.mod_eq_of_lt

      have : NeZero (2 * n + 1) := ⟨by omega⟩
      rw [Fin.val_one']
      exact Nat.mod_eq_of_lt (by omega)
  2. For any vertex u ≠ v, the difference u - v is nonzero and satisfies 1 ≤ (u - v).val < 2n + 1.

    If u - v = 0, then u = v by sub_eq_zero.mp, contradicting u ≠ v. Since u - v ≠ 0, its numerical representative in Fin (2n + 1) is nonzero, so 1 ≤ (u - v).val. The upper bound (u - v).val < 2n + 1 is the defining property of Fin (2n + 1).

    lines 9–21

    uses odd_cycle_is_factor_critical_one_val, sub_eq_zero.mp

      have h1 := odd_cycle_is_factor_critical_one_val hn
      have h_ne : u - v ≠ 0 := by
        intro h
        apply huv
        exact sub_eq_zero.mp h
      have h_pos : 1 ≤ (u - v).val := by
        have : (u - v).val ≠ 0 := by
          intro h
          apply h_ne
          ext
          exact h
        omega
      have h_lt : (u - v).val < 2 * n + 1 := (u - v).isLt
  3. If (u - v).val is odd, then u + 1 ≠ v.

    Suppose for contradiction that u + 1 = v. Then (u + 1) - v = 0, which rearranges to (u - v) + 1 = 0 in Fin (2n + 1). Passing to natural numbers, (u - v).val + 1 is a multiple of 2n + 1. Because 1 ≤ (u - v).val < 2n + 1, the only multiple in range is 2n + 1, which implies (u - v).val = 2n. But 2n is even, contradicting that (u - v).val is odd.

    lines 22–32

    uses sub_eq_zero.mpr, add_sub_right_comm, Fin.val_add, Nat.dvd_of_mod_eq_zero, Nat.le_of_dvd

      split_ifs with h_odd
      · intro h_eq
        have : (u + 1) - v = 0 := sub_eq_zero.mpr h_eq
        rw [add_sub_right_comm] at this
        have h_val : ((u - v + 1 : Fin (2 * n + 1)) : ℕ) = 0 := by rw [this]; rfl
        rw [Fin.val_add, h1] at h_val
        have h_div : (2 * n + 1) ∣ ((u - v).val + 1) := Nat.dvd_of_mod_eq_zero h_val
        have h_le : 2 * n + 1 ≤ (u - v).val + 1 := Nat.le_of_dvd (by omega) h_div
        have h_eq' : (u - v).val = 2 * n := by omega
        have h_mod : (u - v).val % 2 = 0 := by rw [h_eq']; omega
        omega
  4. If (u - v).val is even, then u - 1 ≠ v.

    Suppose for contradiction that u - 1 = v. Then (u - 1) - v = 0, which rearranges to (u - v) - 1 = 0, meaning u - v = 1 in Fin (2n + 1). Taking numerical values shows (u - v).val = 1, which is odd, contradicting that (u - v).val is even.

    lines 33–39

    uses sub_eq_zero.mpr, sub_right_comm, sub_eq_zero.mp

      · intro h_eq
        have : (u - 1) - v = 0 := sub_eq_zero.mpr h_eq
        rw [sub_right_comm] at this
        have : u - v = 1 := sub_eq_zero.mp this
        have h_val : (u - v).val = 1 := by rw [this, h1]
        have : (u - v).val % 2 = 1 := by rw [h_val]
        exact h_odd this
  5. Introduce the candidate matching map f and establish basic bounds on (u - v).val.

    We define f(x) to be x + 1 if (x - v).val is odd and x - 1 if it is even. Since u ≠ v, the difference u - v is nonzero, giving 1 ≤ (u - v).val < 2n + 1 as in earlier lemmas.

    lines 44–57

    uses odd_cycle_is_factor_critical_one_val, sub_eq_zero.mp

      intro f
      have h1 := odd_cycle_is_factor_critical_one_val hn
      have h_ne : u - v ≠ 0 := by
        intro h
        apply huv
        exact sub_eq_zero.mp h
      have h_pos : 1 ≤ (u - v).val := by
        have : (u - v).val ≠ 0 := by
          intro h
          apply h_ne
          ext
          exact h
        omega
      have h_lt : (u - v).val < 2 * n + 1 := (u - v).isLt
  6. If (u - v).val is odd, then f (f u) = u.

    Since (u - v).val is odd, f(u) = u + 1. Because (u - v).val < 2n + 1 is odd, it cannot equal 2n, so (u - v).val < 2n. Thus the offset ((u + 1) - v).val = (u - v).val + 1 does not wrap modulo 2n + 1, and adding 1 changes the parity from odd to even. By definition of f on even offsets, applying f to u + 1 subtracts 1, giving (u + 1) - 1 = u.

    lines 58–76

    uses if_pos, add_sub_right_comm, Fin.val_add, Nat.mod_eq_of_lt, if_neg, add_sub_cancel_right

      by_cases h_odd : (u - v).val % 2 = 1
      · have hfu : f u = u + 1 := by dsimp [f]; rw [if_pos h_odd]
        rw [hfu]
        dsimp [f]
        have h_lt2 : (u - v).val < 2 * n := by
          have : (u - v).val ≤ 2 * n := by omega
          have : (u - v).val ≠ 2 * n := by
            intro heq
            have : (u - v).val % 2 = 0 := by rw [heq]; omega
            omega
          omega
        have h_u'_sub_v : (u + 1) - v = (u - v) + 1 := by rw [add_sub_right_comm]
        have h_val : ((u + 1 - v : Fin (2 * n + 1)) : ℕ) = (u - v).val + 1 := by
          rw [h_u'_sub_v, Fin.val_add, h1, Nat.mod_eq_of_lt (by omega)]
        have h_not_odd : ¬ ((u + 1 - v).val % 2 = 1) := by
          rw [h_val]
          omega
        rw [if_neg h_not_odd]
        exact add_sub_cancel_right u 1
  7. If (u - v).val is even, then f (f u) = u.

    Since (u - v).val is even, f(u) = u - 1. Because u - v ≠ 0, subtracting 1 does not wrap around: ((u - 1) - v).val = (u - v).val - 1, which is odd. Applying f to u - 1 therefore adds 1, yielding (u - 1) + 1 = u.

    lines 77–87

    uses if_neg, sub_right_comm, Fin.val_sub_one_of_ne_zero, if_pos, sub_add_cancel

      · have hfu : f u = u - 1 := by dsimp [f]; rw [if_neg h_odd]
        rw [hfu]
        dsimp [f]
        have h_u'_sub_v : (u - 1) - v = (u - v) - 1 := by rw [sub_right_comm]
        have h_val : ((u - 1 - v : Fin (2 * n + 1)) : ℕ) = (u - v).val - 1 := by
          rw [h_u'_sub_v, Fin.val_sub_one_of_ne_zero h_ne]
        have h_is_odd : (u - 1 - v).val % 2 = 1 := by
          rw [h_val]
          omega
        rw [if_pos h_is_odd]
        exact sub_add_cancel u 1
  8. For every vertex u, u is adjacent to f(u) in C_(2n+1).

    In the cycle graph C_(2n+1), two vertices are adjacent if and only if their difference in either direction equals 1. If (u - v).val is odd, f(u) = u + 1, so (u + 1) - u = 1. If (u - v).val is even, f(u) = u - 1, so u - (u - 1) = 1. In both branches, adjacency holds.

    lines 92–102

    uses odd_cycle_is_factor_critical_one_val, SimpleGraph.cycleGraph_adj', add_sub_cancel_left, sub_sub_cancel

      intro f
      have h1 := odd_cycle_is_factor_critical_one_val hn
      rw [SimpleGraph.cycleGraph_adj']
      dsimp [f]
      split_ifs
      · right
        have : u + 1 - u = 1 := add_sub_cancel_left (u : Fin (2 * n + 1)) 1
        rw [this, h1]
      · left
        have : u - (u - 1) = 1 := sub_sub_cancel u 1
        rw [this, h1]
  9. Given a deleted vertex v, define the induced subgraph H = C_(2n+1) \ {v} and the restricted matching map σ on its vertices.

    Let s = {v}ᶜ and H = G[s] be the induced subgraph. Using odd_cycle_is_factor_critical_ne_v (which shows f(u) ≠ v for all u ≠ v), the map f restricts to a well-defined function σ : s → s on the remaining vertices.

    lines 107–112

    uses odd_cycle_is_factor_critical_ne_v

      intro v
      let G := SimpleGraph.cycleGraph (2 * n + 1)
      let s : Set (Fin (2 * n + 1)) := {v}ᶜ
      let H := G.induce s
      let f := fun (x : Fin (2 * n + 1)) => if (x - v).val % 2 = 1 then x + 1 else x - 1
      let σ : s → s := fun u => ⟨f u.1, odd_cycle_is_factor_critical_ne_v hn v u.1 u.2⟩
  10. The map σ : s → s is an involution: σ (σ x) = x for all x ∈ s.

    By Subtype.ext, equality of subtype elements reduces to equality of their underlying values in Fin (2n + 1). The result then follows directly from odd_cycle_is_factor_critical_f_f, which shows f (f x) = x.

    lines 113–116

    uses Subtype.ext, odd_cycle_is_factor_critical_f_f

      have h_inv : ∀ x, σ (σ x) = x := by
        intro x
        apply Subtype.ext
        exact odd_cycle_is_factor_critical_f_f hn v x.1 x.2
  11. Every vertex x ∈ s is adjacent to σ(x) in the induced subgraph H.

    Adjacency in the induced subgraph H is equivalent to adjacency in G by SimpleGraph.induce_adj. Applying odd_cycle_is_factor_critical_adj shows that x is adjacent to f(x) = σ(x) in G, hence also in H.

    lines 117–120

    uses SimpleGraph.induce_adj, odd_cycle_is_factor_critical_adj

      have h_adj : ∀ x, H.Adj x (σ x) := by
        intro x
        rw [SimpleGraph.induce_adj]
        exact odd_cycle_is_factor_critical_adj hn v x.1
  12. Construct a subgraph M of H with vertex set s and edges {x, y} where y = σ(x).

    We define M as a subgraph on the universal set of vertices of H, with adjacency relation y = σ(x). Every such edge belongs to H because each x is adjacent to σ(x) in H. The edge relation is symmetric because σ is an involution: if y = σ(x), then σ(y) = σ(σ(x)) = x, so x = σ(y).

    lines 121–132

    uses Set.mem_univ

      let M : H.Subgraph := {
        verts := Set.univ
        Adj := fun x y => y = σ x
        adj_sub := by
          intro x y hxy
          rw [hxy]
          exact h_adj x
        edge_vert := fun _ => Set.mem_univ _
        symm := ⟨by
          intro x y hxy
          rw [hxy, h_inv]⟩
      }
  13. M is a perfect matching of H, proving that C_(2n+1) is factor-critical.

    A subgraph is a perfect matching if and only if every vertex has a unique neighbor. For each vertex x ∈ s, σ(x) is a neighbor by definition of M, and if y is any neighbor of x in M, the definition of M requires y = σ(x). Thus every vertex has a unique matched partner, completing the proof.

    lines 133–138

    uses SimpleGraph.Subgraph.isPerfectMatching_iff

      refine ⟨M, ?_⟩
      rw [SimpleGraph.Subgraph.isPerfectMatching_iff]
      intro x
      refine ⟨σ x, rfl, ?_⟩
      intro y hy
      exact hy
Fin.val_one'
In Fin n with n ≠ 0, the numerical value of 1 is 1 % n.
Nat.mod_eq_of_lt
If a < b, then a % b = a.
odd_cycle_is_factor_critical_one_val
For n ≥ 1, the canonical coercion of 1 in Fin (2n + 1) to ℕ equals 1.
sub_eq_zero.mp
In an additive group, if a - b = 0 then a = b.
sub_eq_zero.mpr
In an additive group, if a = b then a - b = 0.
add_sub_right_comm
In an additive commutative group, (a + b) - c = (a - c) + b.
Fin.val_add
The numerical value of a + b in Fin n is (a.val + b.val) % n.
Nat.dvd_of_mod_eq_zero
If n % m = 0, then m divides n.
Nat.le_of_dvd
If m divides n and n > 0, then m ≤ n.
sub_right_comm
In an additive group, (a - b) - c = (a - c) - b.
if_pos
If proposition P holds, then (if P then t else e) = t.
if_neg
If proposition P is false, then (if P then t else e) = e.
add_sub_cancel_right
In an additive group, (a + b) - b = a.
Fin.val_sub_one_of_ne_zero
For a nonzero element i in Fin n, the numerical value of i - 1 is i.val - 1.
sub_add_cancel
In an additive group, (a - b) + b = a.
SimpleGraph.cycleGraph_adj'
Two vertices in the cycle graph C_n are adjacent if and only if their difference in either direction is 1.
add_sub_cancel_left
In an additive group, (a + b) - a = b.
sub_sub_cancel
In an additive group, a - (a - b) = b.
odd_cycle_is_factor_critical_ne_v
The candidate matching map f on Fin (2n + 1) never maps any vertex u ≠ v to v.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
odd_cycle_is_factor_critical_f_f
The candidate matching map f is an involution on vertices distinct from v: f (f u) = u.
SimpleGraph.induce_adj
Two vertices in an induced subgraph are adjacent if and only if they are adjacent in the host graph.
odd_cycle_is_factor_critical_adj
Every vertex u is adjacent to f(u) in the cycle graph C_(2n+1).
Set.mem_univ
Every element belongs to the universal set Set.univ.
SimpleGraph.Subgraph.isPerfectMatching_iff
A subgraph is a perfect matching if and only if every vertex in the host graph has a unique neighbor in the subgraph.

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 odd_cycle_is_factor_critical_one_val {n : ℕ} (hn : 1 ≤ n) :    ((1 : Fin (2 * n + 1)) : ℕ) = 1 := by  have : NeZero (2 * n + 1) := ⟨by omega⟩  rw [Fin.val_one']  exact Nat.mod_eq_of_lt (by omega)lemma odd_cycle_is_factor_critical_ne_v {n : ℕ} (hn : 1 ≤ n) (v u : Fin (2 * n + 1)) (huv : u ≠ v) :    (if (u - v).val % 2 = 1 then u + 1 else u - 1) ≠ v := by  have h1 := odd_cycle_is_factor_critical_one_val hn  have h_ne : u - v ≠ 0 := by    intro h    apply huv    exact sub_eq_zero.mp h  have h_pos : 1 ≤ (u - v).val := by    have : (u - v).val ≠ 0 := by      intro h      apply h_ne      ext      exact h    omega  have h_lt : (u - v).val < 2 * n + 1 := (u - v).isLt  split_ifs with h_odd  · intro h_eq    have : (u + 1) - v = 0 := sub_eq_zero.mpr h_eq    rw [add_sub_right_comm] at this    have h_val : ((u - v + 1 : Fin (2 * n + 1)) : ℕ) = 0 := by rw [this]; rfl    rw [Fin.val_add, h1] at h_val    have h_div : (2 * n + 1) ∣ ((u - v).val + 1) := Nat.dvd_of_mod_eq_zero h_val    have h_le : 2 * n + 1 ≤ (u - v).val + 1 := Nat.le_of_dvd (by omega) h_div    have h_eq' : (u - v).val = 2 * n := by omega    have h_mod : (u - v).val % 2 = 0 := by rw [h_eq']; omega    omega  · intro h_eq    have : (u - 1) - v = 0 := sub_eq_zero.mpr h_eq    rw [sub_right_comm] at this    have : u - v = 1 := sub_eq_zero.mp this    have h_val : (u - v).val = 1 := by rw [this, h1]    have : (u - v).val % 2 = 1 := by rw [h_val]    exact h_odd thislemma odd_cycle_is_factor_critical_f_f {n : ℕ} (hn : 1 ≤ n) (v u : Fin (2 * n + 1)) (huv : u ≠ v) :    let f := fun (x : Fin (2 * n + 1)) => if (x - v).val % 2 = 1 then x + 1 else x - 1    f (f u) = u := by  intro f  have h1 := odd_cycle_is_factor_critical_one_val hn  have h_ne : u - v ≠ 0 := by    intro h    apply huv    exact sub_eq_zero.mp h  have h_pos : 1 ≤ (u - v).val := by    have : (u - v).val ≠ 0 := by      intro h      apply h_ne      ext      exact h    omega  have h_lt : (u - v).val < 2 * n + 1 := (u - v).isLt  by_cases h_odd : (u - v).val % 2 = 1  · have hfu : f u = u + 1 := by dsimp [f]; rw [if_pos h_odd]    rw [hfu]    dsimp [f]    have h_lt2 : (u - v).val < 2 * n := by      have : (u - v).val ≤ 2 * n := by omega      have : (u - v).val ≠ 2 * n := by        intro heq        have : (u - v).val % 2 = 0 := by rw [heq]; omega        omega      omega    have h_u'_sub_v : (u + 1) - v = (u - v) + 1 := by rw [add_sub_right_comm]    have h_val : ((u + 1 - v : Fin (2 * n + 1)) : ℕ) = (u - v).val + 1 := by      rw [h_u'_sub_v, Fin.val_add, h1, Nat.mod_eq_of_lt (by omega)]    have h_not_odd : ¬ ((u + 1 - v).val % 2 = 1) := by      rw [h_val]      omega    rw [if_neg h_not_odd]    exact add_sub_cancel_right u 1  · have hfu : f u = u - 1 := by dsimp [f]; rw [if_neg h_odd]    rw [hfu]    dsimp [f]    have h_u'_sub_v : (u - 1) - v = (u - v) - 1 := by rw [sub_right_comm]    have h_val : ((u - 1 - v : Fin (2 * n + 1)) : ℕ) = (u - v).val - 1 := by      rw [h_u'_sub_v, Fin.val_sub_one_of_ne_zero h_ne]    have h_is_odd : (u - 1 - v).val % 2 = 1 := by      rw [h_val]      omega    rw [if_pos h_is_odd]    exact sub_add_cancel u 1lemma odd_cycle_is_factor_critical_adj {n : ℕ} (hn : 1 ≤ n) (v u : Fin (2 * n + 1)) :    let f := fun (x : Fin (2 * n + 1)) => if (x - v).val % 2 = 1 then x + 1 else x - 1    (SimpleGraph.cycleGraph (2 * n + 1)).Adj u (f u) := by  intro f  have h1 := odd_cycle_is_factor_critical_one_val hn  rw [SimpleGraph.cycleGraph_adj']  dsimp [f]  split_ifs  · right    have : u + 1 - u = 1 := add_sub_cancel_left (u : Fin (2 * n + 1)) 1    rw [this, h1]  · left    have : u - (u - 1) = 1 := sub_sub_cancel u 1    rw [this, h1]/-- The odd cycle graph C_{2n+1} is factor-critical for any n ≥ 1. -/theorem odd_cycle_is_factor_critical (n : ℕ) (hn : 1 ≤ n) :    IsFactorCritical (SimpleGraph.cycleGraph (2 * n + 1)) := by  intro v  let G := SimpleGraph.cycleGraph (2 * n + 1)  let s : Set (Fin (2 * n + 1)) := {v}ᶜ  let H := G.induce s  let f := fun (x : Fin (2 * n + 1)) => if (x - v).val % 2 = 1 then x + 1 else x - 1  let σ : s → s := fun u => ⟨f u.1, odd_cycle_is_factor_critical_ne_v hn v u.1 u.2⟩  have h_inv : ∀ x, σ (σ x) = x := by    intro x    apply Subtype.ext    exact odd_cycle_is_factor_critical_f_f hn v x.1 x.2  have h_adj : ∀ x, H.Adj x (σ x) := by    intro x    rw [SimpleGraph.induce_adj]    exact odd_cycle_is_factor_critical_adj hn v x.1  let M : H.Subgraph := {    verts := Set.univ    Adj := fun x y => y = σ x    adj_sub := by      intro x y hxy      rw [hxy]      exact h_adj x    edge_vert := fun _ => Set.mem_univ _    symm := ⟨by      intro x y hxy      rw [hxy, h_inv]⟩  }  refine ⟨M, ?_⟩  rw [SimpleGraph.Subgraph.isPerfectMatching_iff]  intro x  refine ⟨σ x, rfl, ?_⟩  intro y hy  exact hy
See it in the graphDiscuss this resultChallenge it