odd_cycle_is_minimal_factor_critical
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.
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).
uses
SimpleGraph.cycleGraph_adj',Fin.ext,odd_cycle_is_factor_critical_one_valrw [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
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.
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
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.
uses
sub_self,congrArg,odd_cycle_is_factor_critical_one_valintro 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
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.
uses
sub_self,congrArg,odd_cycle_is_factor_critical_one_valintro 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
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.
uses
odd_cycle_is_factor_critical,Sym2.inductionOn,SimpleGraph.mem_edgeSet,odd_cycle_is_minimal_factor_critical_adj_iffrefine ⟨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
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.
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
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.
uses
SimpleGraph.Subgraph.isPerfectMatching_iff,SimpleGraph.induce_adjhave 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])
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.
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 _
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.
uses
SimpleGraph.Subgraph.isPerfectMatching_iff,SimpleGraph.induce_adjhave 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 α.
- Vertices of the cycle graph C_{2n+1} are formally elements of Fin (2n+1) (integers modulo 2n+1), so u ± 1 denotes cyclic addition or subtraction. The helper lemmas guarantee that 1 ≠ 0 in Fin (2n+1) when n ≥ 1, preventing wrap-around self-equalities like u = u ± 1.
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_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])