AFTD Auto-Formalizing Theoretical Domains

cycle_seven_is_planar

theoremverified

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

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.

  1. 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.

    lines 3–4

      revert x t
      decide
  2. For 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).

    lines 9–14

    uses Set.toFinite, finsum_eq_sum_of_fintype, Set.ncard_iUnion_of_finite, Set.ncard_le_ncard, Set.subset_univ

      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 simp
  3. 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).

    lines 20–29

    uses Set.ncard_pos, Set.toFinite, Set.ncard_eq_one.mp

      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
  4. 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).

    lines 30–36

    uses Finset.sum_const, Nat.mul_comm, Finset.sum_le_sum, cycle_seven_is_planar_sum_ncard_le

      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
      omega
  5. 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}.

    lines 40–43

    uses Set.nonempty_coe_sort.mp, cycle_seven_is_planar_exists_singleton

      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
  6. 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.

    lines 44–56

    uses Classical.choose_spec

      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)
  7. 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.

    lines 57–65

    uses Set.disjoint_left.mp

      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
  8. 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).

    lines 66–74

    uses Finset.card_image_of_injOn, Finset.mem_image.mp, cycle_seven_is_planar_neighbor_bound

      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
      omega
  9. 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.

    lines 84–92

      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
  10. 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.

    lines 93–100

    uses Set.disjoint_left.mp

      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
  11. 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).

    lines 101–109

    uses Finset.card_image_of_injective, Finset.mem_image.mp, cycle_seven_is_planar_neighbor_bound

      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
      omega
  12. 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.

    lines 113–121

    uses Set.nonempty_coe_sort.mp, cycle_seven_is_planar_exists_singleton, cycle_seven_is_planar_K33_aux

      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)
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.

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

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⟩
See it in the graphDiscuss this resultChallenge it