exists_planar_all_powers_well_covered_diam_eq_three
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
- 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_well_coveredA finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers…
- simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…
- cycle_seven_all_powers_well_coveredFor every positive integer d, the d-th power of the 7-cycle graph C_7 is well-covered.
- cycle_seven_diam_eq_threeThe diameter of the 7-cycle graph C_7 is equal to 3.
- cycle_seven_is_planarThe 7-cycle graph C_7 is planar.
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.
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.
refine ⟨Fin 7, inferInstance, SimpleGraph.cycleGraph 7, ?_, ?_, ?_, ?_, ?_⟩C₇ is connected.
Every cycle graph on at least one vertex (here 6 + 1 = 7) is connected.
uses
SimpleGraph.cycleGraph_connected· exact SimpleGraph.cycleGraph_connectedC₇ is planar.
Planarity of C₇ is provided by the helper theorem cycle_seven_is_planar.
uses
cycle_seven_is_planar· exact cycle_seven_is_planarThe 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.
· simpThe 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.
uses
cycle_seven_diam_eq_three· exact cycle_seven_diam_eq_threeEvery 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.
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.
- The substantive graph-theoretic verification—that the 7-cycle graph C₇ is planar, has diameter 3, and has all positive powers well-covered—is established in separate helper lemmas; this theorem packages them together with C₇ as the constructive witness.
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.
/-- 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