odd_cycle_is_factor_critical
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
- odd_cycle_is_minimal_factor_criticalFor every integer n ≥ 1, the odd cycle graph C_{2n+1} is minimal factor-critical.
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.
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.
uses
Fin.val_one',Nat.mod_eq_of_lthave : NeZero (2 * n + 1) := ⟨by omega⟩ rw [Fin.val_one'] exact Nat.mod_eq_of_lt (by omega)
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).
uses
odd_cycle_is_factor_critical_one_val,sub_eq_zero.mphave 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
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.
uses
sub_eq_zero.mpr,add_sub_right_comm,Fin.val_add,Nat.dvd_of_mod_eq_zero,Nat.le_of_dvdsplit_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
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.
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
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.
uses
odd_cycle_is_factor_critical_one_val,sub_eq_zero.mpintro 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
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.
uses
if_pos,add_sub_right_comm,Fin.val_add,Nat.mod_eq_of_lt,if_neg,add_sub_cancel_rightby_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
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.
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
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.
uses
odd_cycle_is_factor_critical_one_val,SimpleGraph.cycleGraph_adj',add_sub_cancel_left,sub_sub_cancelintro 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]
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.
uses
odd_cycle_is_factor_critical_ne_vintro 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⟩
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.
uses
Subtype.ext,odd_cycle_is_factor_critical_f_fhave 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
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.
uses
SimpleGraph.induce_adj,odd_cycle_is_factor_critical_adjhave 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
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).
uses
Set.mem_univlet 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]⟩ }
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.
uses
SimpleGraph.Subgraph.isPerfectMatching_iffrefine ⟨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.
- Linear arithmetic tactic omega is used extensively to discharge modular bounds, verify parities, and derive arithmetic contradictions from divisibility.
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 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