AFTD Auto-Formalizing Theoretical Domains

exists_planar_all_powers_well_covered_diam_eq_three

theoremverifiedoriginal

There exists a finite connected simple planar graph G with at least two vertices whose diameter is exactly 3 and such that every positive integer power G^d (for d ≥ 1) is well-covered.

Statement

theorem exists_planar_all_powers_well_covered_diam_eq_three :
    ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V),
      G.Connected ∧
      simple_graph_is_planar G ∧
      2 ≤ Fintype.card V ∧
      G.diam = 3 ∧
      (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d))
Related work
arXiv:2610.09300 Example 3.8; OP-537
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6

Read back from the Lean

There exists a finite type $V$ and a simple graph $G$ on $V$ such that: 1. $G$ is connected; 2. $G$ is planar (defined as not having $K_5$ or $K_{3,3}$ as a graph minor); 3. the number of vertices of $V$ is at least 2; 4. the diameter of $G$ is equal to 3; and 5. for every natural number $d \ge 1$, the $d$-th power of $G$ is well-covered (meaning all maximal independent sets in the $d$-th power of $G$ have the same cardinality).

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 theorem is proved constructively by exhibiting the 7-cycle graph C₇ on seven vertices as an explicit witness. This reduces the problem to verifying five conditions: connectedness, planarity, having at least two vertices, having diameter 3, and having every positive power well-covered. Each condition is discharged by an existing helper theorem about C₇ or by direct arithmetic evaluation.

  1. The 7-cycle graph C₇ on the vertex set Fin 7 is chosen as the witness, reducing the existential goal to five subgoals.

    We instantiate the existential quantifiers with the vertex type Fin 7, its canonical finite instance, and the cycle graph C₇. This leaves five properties to prove for C₇: connectedness, planarity, having at least two vertices, having diameter 3, and having every positive power well-covered.

    line 9

      refine ⟨Fin 7, inferInstance, SimpleGraph.cycleGraph 7, ?_, ?_, ?_, ?_, ?_⟩
  2. C₇ is connected.

    Every cycle graph on at least one vertex (here 6 + 1 = 7) is connected.

    line 10

    uses SimpleGraph.cycleGraph_connected

      · exact SimpleGraph.cycleGraph_connected
  3. C₇ is planar.

    Planarity of C₇ is provided by the helper theorem cycle_seven_is_planar.

    line 11

    uses cycle_seven_is_planar

      · exact cycle_seven_is_planar
  4. The vertex set of C₇ has cardinality at least 2.

    The simplifier computes the cardinality of Fin 7 as 7 and verifies the numerical inequality 2 ≤ 7.

    line 12

      · simp
  5. The diameter of C₇ is 3.

    The diameter of the 7-cycle graph is known to be ⌊7/2⌋ = 3, as formalized in cycle_seven_diam_eq_three.

    line 13

    uses cycle_seven_diam_eq_three

      · exact cycle_seven_diam_eq_three
  6. Every positive power of C₇ is well-covered.

    The helper theorem cycle_seven_all_powers_well_covered shows that for any d ≥ 1, all maximal independent sets of (C₇)^d have the same cardinality.

    line 14

    uses cycle_seven_all_powers_well_covered

      · exact cycle_seven_all_powers_well_covered
SimpleGraph.cycleGraph_connected
For every natural number n, the cycle graph on n + 1 vertices is connected.
cycle_seven_is_planar
The 7-cycle graph C₇ is planar, meaning it does not contain K₅ or K₃,₃ as a minor.
cycle_seven_diam_eq_three
The diameter of the 7-cycle graph C₇ is equal to 3.
cycle_seven_all_powers_well_covered
For every integer d ≥ 1, the d-th graph power of the 7-cycle graph C₇ is well-covered.

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

/-- Sharpness of the diameter bound in OP-537: there exists a connected planar graph of diameter 3 with all powers well-covered. -/theorem exists_planar_all_powers_well_covered_diam_eq_three :    ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V),      G.Connected ∧      simple_graph_is_planar G ∧      2 ≤ Fintype.card V ∧      G.diam = 3 ∧      (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) := by  refine ⟨Fin 7, inferInstance, SimpleGraph.cycleGraph 7, ?_, ?_, ?_, ?_, ?_⟩  · exact SimpleGraph.cycleGraph_connected  · exact cycle_seven_is_planar  · simp  · exact cycle_seven_diam_eq_three  · exact cycle_seven_all_powers_well_covered
See it in the graphDiscuss this resultChallenge it