cycle_seven_is_planar
The 7-cycle graph C_7 is planar.
Statement
theorem cycle_seven_is_planar : simple_graph_is_planar (SimpleGraph.cycleGraph 7)- Source
- folklore; OP-537
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_is_planarA simple graph G is planar by Wagner's criterion if neither the complete graph on 5 vertices nor the complete bipartite graph K_{3,3} is a…
- simple_graph_is_minorA graph H is a minor of a graph G if there exists a family of pairwise disjoint, non-empty, connected subsets B_u of V(G) indexed by u in…
- Used by 1
- exists_planar_all_powers_well_covered_diam_eq_threeThere exists a finite connected simple planar graph G with at least two vertices whose diameter is exactly 3 and such that every positive…
Read back from the Lean
The cycle graph on 7 vertices (SimpleGraph.cycleGraph 7) is planar, in the sense that it contains neither the complete graph on 5 vertices ($K_5$, ⊤ : SimpleGraph (Fin 5)) nor the complete bipartite graph $K_{3,3}$ (completeBipartiteGraph (Fin 3) (Fin 3)) as a graph minor.
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 establishes that the 7-cycle graph C_7 is planar by verifying the forbidden-minor criterion (the definition of `simple_graph_is_planar`): C_7 contains neither K_5 nor K_{3,3} as a minor. In both cases, a pigeonhole argument on the sum of branch set sizes shows that any minor embedding into a 7-vertex graph would force at least one branch set to be a singleton {x}. That singleton vertex would then need to be adjacent in C_7 to at least 4 distinct branch sets (for K_5) or at least 3 distinct branch sets (for K_{3,3}), directly contradicting the fact that every vertex in C_7 has degree at most 2.
Any vertex in the 7-cycle graph C_7 has at most 2 neighbors. automation
Reverting the vertex x and subset t leaves a finite combinatorial statement over the 7-element set Fin 7, which the decide tactic proves by exhaustive finite evaluation.
revert x t decideFor any family of pairwise disjoint subsets B_i ⊆ Fin 7, the sum of their cardinalities is at most 7.
Because Fin 7 is finite, each B_i is finite (by Set.toFinite). For pairwise disjoint finite sets, the sum of cardinalities equals the cardinality of their union (by finsum_eq_sum_of_fintype and Set.ncard_iUnion_of_finite). Since the union is a subset of the universal set of Fin 7 (Set.subset_univ), its cardinality is at most |Fin 7| = 7 (by Set.ncard_le_ncard).
uses
Set.toFinite,finsum_eq_sum_of_fintype,Set.ncard_iUnion_of_finite,Set.ncard_le_ncard,Set.subset_univhave hfin : ∀ i, (B i).Finite := fun i => Set.toFinite _ have hpd : Pairwise (Function.onFun Disjoint B) := hdisj rw [← finsum_eq_sum_of_fintype (fun i => (B i).ncard)] rw [← Set.ncard_iUnion_of_finite hfin hpd] calc (⋃ i, B i).ncard ≤ (Set.univ : Set (Fin 7)).ncard := Set.ncard_le_ncard (Set.subset_univ _) _ = 7 := by simp
Assuming for contradiction that no B_i is a singleton, each B_i must have cardinality at least 2.
By contradiction, suppose no B_i is of the form {x}. Since each B_i is nonempty, its cardinality is at least 1 (by Set.ncard_pos and Set.toFinite). If its cardinality were 1, it would be a singleton {a} (by Set.ncard_eq_one.mp), contradicting the hypothesis. Therefore, the cardinality cannot be 1, so it must be at least 2 (closed by omega).
uses
Set.ncard_pos,Set.toFinite,Set.ncard_eq_one.mpby_contra h push Not at h have h2 : ∀ i, 2 ≤ (B i).ncard := by intro i have hpos : 1 ≤ (B i).ncard := (Set.ncard_pos (Set.toFinite _)).mpr (hne i) have hne1 : (B i).ncard ≠ 1 := by intro h1 obtain ⟨a, ha⟩ := Set.ncard_eq_one.mp h1 exact h i a ha omega
If 7 < 2 * |ι|, at least one subset B_i in the disjoint family must be a singleton.
Summing the lower bound |B_i| ≥ 2 over all indices in ι gives ∑_i |B_i| ≥ 2 * |ι| (by Finset.sum_le_sum, Finset.sum_const, and Nat.mul_comm). Since 2 * |ι| > 7, this implies ∑_i |B_i| > 7, directly contradicting the upper bound ∑_i |B_i| ≤ 7 from cycle_seven_is_planar_sum_ncard_le (closed by omega).
uses
Finset.sum_const,Nat.mul_comm,Finset.sum_le_sum,cycle_seven_is_planar_sum_ncard_lehave hsum2 : (∑ _i : ι, (2:ℕ)) = 2 * Fintype.card ι := by simp [Finset.sum_const, Nat.mul_comm] have hge : 2 * Fintype.card ι ≤ ∑ i, (B i).ncard := by have hle : (∑ _i : ι, (2:ℕ)) ≤ ∑ i, (B i).ncard := Finset.sum_le_sum (fun i _ => h2 i) rwa [hsum2] at hle have hle := cycle_seven_is_planar_sum_ncard_le B hdisj omega
If K_5 is a minor of C_7, there is an index u ∈ Fin 5 whose branch set B_u is a singleton {x}.
Unpacking the minor definition gives pairwise disjoint, connected, nonempty branch sets B_i for each vertex of K_5 (using Set.nonempty_coe_sort.mp). Since 7 < 2 * 5 = 10, cycle_seven_is_planar_exists_singleton provides a singleton branch set B_u = {x}.
uses
Set.nonempty_coe_sort.mp,cycle_seven_is_planar_exists_singletonclassical rintro ⟨B, hconn, hdisj, hadj⟩ have hne : ∀ i, (B i).Nonempty := fun i => Set.nonempty_coe_sort.mp (hconn i).nonempty obtain ⟨u, x, hx⟩ := cycle_seven_is_planar_exists_singleton (ι := Fin 5) (by norm_num) B hne hdisj
For each of the other 4 vertices v ≠ u in K_5, there is a vertex f(v) ∈ B_v adjacent to x in C_7.
Since u and v are distinct vertices in K_5, they are adjacent. By the definition of minor, there exist x' ∈ B_u and y ∈ B_v adjacent in C_7. Because B_u = {x}, x' must equal x, so y is a neighbor of x in B_v. Using Classical.choose_spec, we define f(v) to be such a chosen neighbor for each v ≠ u.
uses
Classical.choose_spechave hwit : ∀ v : Fin 5, v ≠ u → ∃ y ∈ B v, (SimpleGraph.cycleGraph 7).Adj x y := by intro v hv obtain ⟨x', hx'u, y, hyv, hadj'⟩ := hadj u v (by simpa using hv.symm) have hx' : x' = x := by have h1 : x' ∈ ({x} : Set (Fin 7)) := hx ▸ hx'u simpa using h1 exact ⟨y, hyv, by simpa [hx'] using hadj'⟩ set f : Fin 5 → Fin 7 := fun v => if h : v = u then x else Classical.choose (hwit v h) with hfdef have hf_spec : ∀ v (hv : v ≠ u), f v ∈ B v ∧ (SimpleGraph.cycleGraph 7).Adj x (f v) := by intro v hv have heq : f v = Classical.choose (hwit v hv) := by simp [hfdef, hv] rw [heq] exact Classical.choose_spec (hwit v hv)
The chosen neighbor assignment f is injective on Fin 5 \ {u}.
If f(v) = f(w) for distinct v, w ≠ u, then the element f(v) belongs to both B_v and B_w. However, distinct branch sets are disjoint, so no element can belong to both (by Set.disjoint_left.mp), a contradiction.
uses
Set.disjoint_left.mphave hinj : Set.InjOn f ↑(Finset.univ.erase u) := by intro v hv w hw hvw have hv' : v ≠ u := by simpa using hv have hw' : w ≠ u := by simpa using hw by_contra hne have h1 : f v ∈ B v := (hf_spec v hv').1 have h2 : f w ∈ B w := (hf_spec w hw').1 have h3 : f v ∈ B w := by rw [hvw]; exact h2 exact (Set.disjoint_left.mp (hdisj v w hne)) h1 h3
The complete graph K_5 is not a minor of C_7.
Since f is injective on the 4-element set Fin 5 \ {u}, its image contains 4 distinct vertices (by Finset.card_image_of_injOn), all of which are adjacent to x in C_7 (by Finset.mem_image.mp). This contradicts cycle_seven_is_planar_neighbor_bound, which states that x can have at most 2 neighbors in C_7 (closed by omega).
uses
Finset.card_image_of_injOn,Finset.mem_image.mp,cycle_seven_is_planar_neighbor_boundhave hcard : ((Finset.univ.erase u).image f).card = 4 := by rw [Finset.card_image_of_injOn hinj] simp have hall : ∀ y ∈ (Finset.univ.erase u).image f, (SimpleGraph.cycleGraph 7).Adj x y := by intro y hy obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp hy exact (hf_spec v (by simpa using hv)).2 have := cycle_seven_is_planar_neighbor_bound x _ hall omega
In a K_{3,3} minor embedding, choosing an edge from {x} to each branch set B_{g(j)} gives a neighbor f(j) of x.
For each j ∈ Fin 3, since u is adjacent to g(j) in K_{3,3}, the minor property provides an edge between B_u = {x} and B_{g(j)}. Because B_u is a singleton, the endpoint in B_u must be x, leaving an adjacent vertex y ∈ B_{g(j)}. The choose tactic defines f and extracts this specification.
classical have key : ∀ j : Fin 3, ∃ y ∈ B (g j), (SimpleGraph.cycleGraph 7).Adj x y := by intro j obtain ⟨x', hx'u, y, hyv, hadj'⟩ := hadj u (g j) (hg_adj j) have hx' : x' = x := by have h1 : x' ∈ ({x} : Set (Fin 7)) := hx ▸ hx'u simpa using h1 exact ⟨y, hyv, by simpa [hx'] using hadj'⟩ choose f hf using key
The map f from Fin 3 to Fin 7 is injective.
If f(i) = f(j) for i ≠ j, then since g is injective, g(i) ≠ g(j). Thus B_{g(i)} and B_{g(j)} are disjoint branch sets (by Set.disjoint_left.mp), which contradicts that f(i) belongs to both.
uses
Set.disjoint_left.mphave hinj : Function.Injective f := by intro i j hij by_contra hne have h1 : f i ∈ B (g i) := (hf i).1 have h2 : f j ∈ B (g j) := (hf j).1 have h3 : f i ∈ B (g j) := by rw [hij]; exact h2 have hgij : g i ≠ g j := fun h => hne (hg_inj h) exact (Set.disjoint_left.mp (hdisj _ _ hgij)) h1 h3
No vertex in a K_{3,3} minor can have a singleton branch set adjacent to 3 distinct branch sets.
Since f is injective on Fin 3, the image of Fin 3 under f has cardinality 3 (by Finset.card_image_of_injective). All 3 vertices are adjacent to x in C_7 (by Finset.mem_image.mp), which contradicts cycle_seven_is_planar_neighbor_bound allowing at most 2 neighbors (closed by omega).
uses
Finset.card_image_of_injective,Finset.mem_image.mp,cycle_seven_is_planar_neighbor_boundhave hcard : (Finset.univ.image f).card = 3 := by rw [Finset.card_image_of_injective _ hinj] simp have hall : ∀ y ∈ Finset.univ.image f, (SimpleGraph.cycleGraph 7).Adj x y := by intro y hy obtain ⟨j, _, rfl⟩ := Finset.mem_image.mp hy exact (hf j).2 have hb := cycle_seven_is_planar_neighbor_bound x _ hall omega
The complete bipartite graph K_{3,3} is not a minor of C_7.
Suppose K_{3,3} is a minor of C_7 with branch sets B indexed by Fin 3 ⊕ Fin 3. Since the branch sets are nonempty (Set.nonempty_coe_sort.mp) and 7 < 2 * 6 = 12, cycle_seven_is_planar_exists_singleton guarantees a singleton branch set B_u = {x}. Depending on whether u is in the left partition (Sum.inl a) or the right partition (Sum.inr b), u is adjacent to all 3 vertices of the other partition, and in both cases cycle_seven_is_planar_K33_aux derives False.
uses
Set.nonempty_coe_sort.mp,cycle_seven_is_planar_exists_singleton,cycle_seven_is_planar_K33_auxclassical rintro ⟨B, hconn, hdisj, hadj⟩ have hne : ∀ i, (B i).Nonempty := fun i => Set.nonempty_coe_sort.mp (hconn i).nonempty obtain ⟨u, x, hx⟩ := cycle_seven_is_planar_exists_singleton (ι := Fin 3 ⊕ Fin 3) (by simp) B hne hdisj rcases u with a | b · exact cycle_seven_is_planar_K33_aux B hdisj hadj (Sum.inl a) x hx (fun j => (Sum.inr j : Fin 3 ⊕ Fin 3)) (by intro i j h; simpa using h) (by simp) · exact cycle_seven_is_planar_K33_aux B hdisj hadj (Sum.inr b) x hx (fun j => (Sum.inl j : Fin 3 ⊕ Fin 3)) (by intro i j h; simpa using h) (by simp)
Classical.choose_spec- The witness produced by the axiom of choice satisfies the predicate it was chosen for.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_image_of_injOn- The image of a finite set under a map that is injective on that set has the same cardinality as the set.
Finset.mem_image.mp- An element belongs to the image of a finite set under a function if and only if it is the value of the function at some element of that set.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set times that constant.
Finset.sum_le_sum- If each term of a finite sum is less than or equal to the corresponding term of another sum, the sum is less than or equal to the other sum.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Set.disjoint_left.mp- If two sets are disjoint, no element belongs to both.
Set.ncard_eq_one.mp- If a set has cardinality 1, then it is a singleton {a} for some element a.
Set.ncard_iUnion_of_finite- The cardinality of a disjoint union of finitely many finite sets is the sum of their cardinalities.
Set.ncard_le_ncard- A subset of a finite set has cardinality less than or equal to that of the ambient set.
Set.ncard_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
Set.nonempty_coe_sort.mp- If the subtype corresponding to a set is nonempty, then the set is nonempty.
Set.subset_univ- Every set is a subset of the universal set.
Set.toFinite- A set whose coercion to a subtype is finite is finite as a set.
cycle_seven_is_planar_exists_singleton- If a finite family of pairwise disjoint nonempty subsets of Fin 7 has index set ι with 7 < 2 * |ι|, at least one subset must be a singleton.
cycle_seven_is_planar_K33_aux- In a minor embedding of K_{3,3} into C_7, no vertex can have a singleton branch set connected to 3 distinct branch sets.
cycle_seven_is_planar_neighbor_bound- Any vertex in the 7-cycle graph C_7 has at most 2 neighbors.
cycle_seven_is_planar_sum_ncard_le- The sum of cardinalities of any family of pairwise disjoint subsets of Fin 7 is at most 7.
finsum_eq_sum_of_fintype- Over a finite type, the unconditioned sum (finsum) equals the standard finite sum.
- The definition of planarity used here (`simple_graph_is_planar`) is combinatorial rather than topological: it directly defines planarity as the absence of both a $K_5$ minor and a $K_{3,3}$ minor, in accordance with Kuratowski's and Wagner's theorems.
- The final theorem `cycle_seven_is_planar` at line 124 is proved in term mode by constructing the pair `⟨cycle_seven_is_planar_not_K5, cycle_seven_is_planar_not_K33⟩`, so it contains no tactic lines.
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.
private lemma cycle_seven_is_planar_neighbor_bound (x : Fin 7) (t : Finset (Fin 7)) (h : ∀ y ∈ t, (SimpleGraph.cycleGraph 7).Adj x y) : t.card ≤ 2 := by revert x t decideprivate lemma cycle_seven_is_planar_sum_ncard_le {ι : Type} [Fintype ι] (B : ι → Set (Fin 7)) (hdisj : ∀ i j, i ≠ j → Disjoint (B i) (B j)) : (∑ i, (B i).ncard) ≤ 7 := by have hfin : ∀ i, (B i).Finite := fun i => Set.toFinite _ have hpd : Pairwise (Function.onFun Disjoint B) := hdisj rw [← finsum_eq_sum_of_fintype (fun i => (B i).ncard)] rw [← Set.ncard_iUnion_of_finite hfin hpd] calc (⋃ i, B i).ncard ≤ (Set.univ : Set (Fin 7)).ncard := Set.ncard_le_ncard (Set.subset_univ _) _ = 7 := by simpprivate lemma cycle_seven_is_planar_exists_singleton {ι : Type} [Fintype ι] (hcard : 7 < 2 * Fintype.card ι) (B : ι → Set (Fin 7)) (hne : ∀ i, (B i).Nonempty) (hdisj : ∀ i j, i ≠ j → Disjoint (B i) (B j)) : ∃ i, ∃ x, B i = {x} := by by_contra h push Not at h have h2 : ∀ i, 2 ≤ (B i).ncard := by intro i have hpos : 1 ≤ (B i).ncard := (Set.ncard_pos (Set.toFinite _)).mpr (hne i) have hne1 : (B i).ncard ≠ 1 := by intro h1 obtain ⟨a, ha⟩ := Set.ncard_eq_one.mp h1 exact h i a ha omega have hsum2 : (∑ _i : ι, (2:ℕ)) = 2 * Fintype.card ι := by simp [Finset.sum_const, Nat.mul_comm] have hge : 2 * Fintype.card ι ≤ ∑ i, (B i).ncard := by have hle : (∑ _i : ι, (2:ℕ)) ≤ ∑ i, (B i).ncard := Finset.sum_le_sum (fun i _ => h2 i) rwa [hsum2] at hle have hle := cycle_seven_is_planar_sum_ncard_le B hdisj omegaprivate lemma cycle_seven_is_planar_not_K5 : ¬ simple_graph_is_minor (⊤ : SimpleGraph (Fin 5)) (SimpleGraph.cycleGraph 7) := by classical rintro ⟨B, hconn, hdisj, hadj⟩ have hne : ∀ i, (B i).Nonempty := fun i => Set.nonempty_coe_sort.mp (hconn i).nonempty obtain ⟨u, x, hx⟩ := cycle_seven_is_planar_exists_singleton (ι := Fin 5) (by norm_num) B hne hdisj have hwit : ∀ v : Fin 5, v ≠ u → ∃ y ∈ B v, (SimpleGraph.cycleGraph 7).Adj x y := by intro v hv obtain ⟨x', hx'u, y, hyv, hadj'⟩ := hadj u v (by simpa using hv.symm) have hx' : x' = x := by have h1 : x' ∈ ({x} : Set (Fin 7)) := hx ▸ hx'u simpa using h1 exact ⟨y, hyv, by simpa [hx'] using hadj'⟩ set f : Fin 5 → Fin 7 := fun v => if h : v = u then x else Classical.choose (hwit v h) with hfdef have hf_spec : ∀ v (hv : v ≠ u), f v ∈ B v ∧ (SimpleGraph.cycleGraph 7).Adj x (f v) := by intro v hv have heq : f v = Classical.choose (hwit v hv) := by simp [hfdef, hv] rw [heq] exact Classical.choose_spec (hwit v hv) have hinj : Set.InjOn f ↑(Finset.univ.erase u) := by intro v hv w hw hvw have hv' : v ≠ u := by simpa using hv have hw' : w ≠ u := by simpa using hw by_contra hne have h1 : f v ∈ B v := (hf_spec v hv').1 have h2 : f w ∈ B w := (hf_spec w hw').1 have h3 : f v ∈ B w := by rw [hvw]; exact h2 exact (Set.disjoint_left.mp (hdisj v w hne)) h1 h3 have hcard : ((Finset.univ.erase u).image f).card = 4 := by rw [Finset.card_image_of_injOn hinj] simp have hall : ∀ y ∈ (Finset.univ.erase u).image f, (SimpleGraph.cycleGraph 7).Adj x y := by intro y hy obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp hy exact (hf_spec v (by simpa using hv)).2 have := cycle_seven_is_planar_neighbor_bound x _ hall omegaprivate lemma cycle_seven_is_planar_K33_aux (B : Fin 3 ⊕ Fin 3 → Set (Fin 7)) (hdisj : ∀ i j, i ≠ j → Disjoint (B i) (B j)) (hadj : ∀ u v, (completeBipartiteGraph (Fin 3) (Fin 3)).Adj u v → ∃ x ∈ B u, ∃ y ∈ B v, (SimpleGraph.cycleGraph 7).Adj x y) (u : Fin 3 ⊕ Fin 3) (x : Fin 7) (hx : B u = {x}) (g : Fin 3 → Fin 3 ⊕ Fin 3) (hg_inj : Function.Injective g) (hg_adj : ∀ j, (completeBipartiteGraph (Fin 3) (Fin 3)).Adj u (g j)) : False := by classical have key : ∀ j : Fin 3, ∃ y ∈ B (g j), (SimpleGraph.cycleGraph 7).Adj x y := by intro j obtain ⟨x', hx'u, y, hyv, hadj'⟩ := hadj u (g j) (hg_adj j) have hx' : x' = x := by have h1 : x' ∈ ({x} : Set (Fin 7)) := hx ▸ hx'u simpa using h1 exact ⟨y, hyv, by simpa [hx'] using hadj'⟩ choose f hf using key have hinj : Function.Injective f := by intro i j hij by_contra hne have h1 : f i ∈ B (g i) := (hf i).1 have h2 : f j ∈ B (g j) := (hf j).1 have h3 : f i ∈ B (g j) := by rw [hij]; exact h2 have hgij : g i ≠ g j := fun h => hne (hg_inj h) exact (Set.disjoint_left.mp (hdisj _ _ hgij)) h1 h3 have hcard : (Finset.univ.image f).card = 3 := by rw [Finset.card_image_of_injective _ hinj] simp have hall : ∀ y ∈ Finset.univ.image f, (SimpleGraph.cycleGraph 7).Adj x y := by intro y hy obtain ⟨j, _, rfl⟩ := Finset.mem_image.mp hy exact (hf j).2 have hb := cycle_seven_is_planar_neighbor_bound x _ hall omegaprivate lemma cycle_seven_is_planar_not_K33 : ¬ simple_graph_is_minor (completeBipartiteGraph (Fin 3) (Fin 3)) (SimpleGraph.cycleGraph 7) := by classical rintro ⟨B, hconn, hdisj, hadj⟩ have hne : ∀ i, (B i).Nonempty := fun i => Set.nonempty_coe_sort.mp (hconn i).nonempty obtain ⟨u, x, hx⟩ := cycle_seven_is_planar_exists_singleton (ι := Fin 3 ⊕ Fin 3) (by simp) B hne hdisj rcases u with a | b · exact cycle_seven_is_planar_K33_aux B hdisj hadj (Sum.inl a) x hx (fun j => (Sum.inr j : Fin 3 ⊕ Fin 3)) (by intro i j h; simpa using h) (by simp) · exact cycle_seven_is_planar_K33_aux B hdisj hadj (Sum.inr b) x hx (fun j => (Sum.inl j : Fin 3 ⊕ Fin 3)) (by intro i j h; simpa using h) (by simp)/-- The 7-cycle graph is planar. -/theorem cycle_seven_is_planar : simple_graph_is_planar (SimpleGraph.cycleGraph 7) := ⟨cycle_seven_is_planar_not_K5, cycle_seven_is_planar_not_K33⟩