complete_graph_two_all_powers_well_covered
The complete graph on 2 vertices K_2 is connected, has diameter 1, and every positive power K_2^d (d ≥ 1) is well-covered.
Statement
theorem complete_graph_two_all_powers_well_covered :
(SimpleGraph.completeGraph (Fin 2)).Connected ∧
(SimpleGraph.completeGraph (Fin 2)).diam = 1 ∧
∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (SimpleGraph.completeGraph (Fin 2)) d)- Source
- arXiv:2611.03956 Lemma 2.8 and Corollary 2.13
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- forall_power_well_covered_of_well_covered_diam_le_twoLet G be a finite connected well-covered graph of diameter at most 2. Then G^d is well-covered for every d ≥ 1.
- 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…
- Used by 1
- exists_connected_all_powers_well_covered_diam_geFor every positive integer D, there exists a finite connected simple graph G with diameter at least D such that every positive power G^d…
Read back from the Lean
The declaration asserts the conjunction of three statements about the complete graph on two vertices, $K_2 = \text{SimpleGraph.completeGraph (Fin 2)}$: 1. $K_2$ is connected; 2. The diameter of $K_2$ is equal to 1; 3. For every natural number $d \ge 1$, the $d$-th power of $K_2$ (the graph with the same vertices where distinct vertices are adjacent if and only if their distance in $K_2$ is at most $d$) is well-covered, meaning that every two maximal independent sets of vertices 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 complete graph K_2 is connected and has diameter 1 because it is the complete graph ⊤ on two vertices. By an existing theorem (`forall_power_well_covered_of_well_covered_diam_le_two`), every positive power of a connected graph of diameter at most 2 is well-covered provided the graph itself is well-covered. The argument therefore reduces to showing that K_2 is well-covered, which holds because every maximal independent set in K_2 cannot be empty (as singletons are independent) and cannot contain two distinct vertices (as distinct vertices in K_2 are adjacent), forcing every maximal independent set to have cardinality 1.
K_2 is connected and has diameter 1.
The complete graph on two vertices (represented as `SimpleGraph.completeGraph (Fin 2)`, which equals ⊤) is connected by `SimpleGraph.connected_top` because its vertex set is nonempty. Furthermore, its diameter is 1 by `SimpleGraph.diam_top`, since the type `Fin 2` has at least two distinct elements.
uses
SimpleGraph.connected_top,SimpleGraph.diam_tophave hconn : (SimpleGraph.completeGraph (Fin 2)).Connected := SimpleGraph.connected_top have hdiam : (SimpleGraph.completeGraph (Fin 2)).diam = 1 := by change (⊤ : SimpleGraph (Fin 2)).diam = 1 exact SimpleGraph.diam_top
It suffices to show that K_2 is well-covered.
We supply the established facts that K_2 is connected and has diameter 1 for the first two conjuncts. For the third conjunct—that every power K_2^d (d ≥ 1) is well-covered—we invoke `forall_power_well_covered_of_well_covered_diam_le_two`. This theorem requires that the graph is connected, has diameter at most 2 (which holds since its diameter is 1 ≤ 2), and is itself well-covered. Hence the goal reduces to showing that K_2 is well-covered.
uses
forall_power_well_covered_of_well_covered_diam_le_tworefine ⟨hconn, hdiam, ?_⟩ apply forall_power_well_covered_of_well_covered_diam_le_two · exact hconn · rw [hdiam] omega
To show that K_2 is well-covered, let s and t be two maximal independent sets; it suffices to show |s| = |t|.
By definition, a graph is well-covered if all its maximal independent sets have the same cardinality. Viewing K_2 as the complete graph ⊤ on `Fin 2`, we introduce two arbitrary maximal independent sets s and t (with maximality hypotheses hs and ht), leaving the goal to show |s| = |t|.
· change simple_graph_is_well_covered (⊤ : SimpleGraph (Fin 2)) intro s t hs ht
Every maximal independent set in K_2 has cardinality 1.
Let u be any maximal independent set in K_2 = ⊤. Pick an arbitrary vertex v0 ∈ Fin 2. We case split on whether u is nonempty: - If u is nonempty, let a ∈ u. To show u = {a} (and therefore |u| = 1 via `Finset.card_eq_one`), suppose for contradiction that there is some b ∈ u with b ≠ a. In the complete graph ⊤, any two distinct vertices are adjacent, which contradicts the independence of u. Thus u = {a} and |u| = 1. - If u is not nonempty, then u = ∅ by `Finset.not_nonempty_iff_eq_empty`. However, any singleton {v0} is trivially an independent set in ⊤. By the maximality of u = ∅ and the fact that ∅ ⊆ {v0} (`Finset.empty_subset`), we obtain {v0} ⊆ ∅, a contradiction. In either case, |u| = 1.
uses
Finset.card_eq_one,Finset.not_nonempty_iff_eq_empty,Finset.empty_subsethave hcard : ∀ u : Finset (Fin 2), Maximal (fun (w : Finset (Fin 2)) => (⊤ : SimpleGraph (Fin 2)).IsIndepSet (w : Set (Fin 2))) u → u.card = 1 := by intro u hu obtain ⟨v0⟩ : Nonempty (Fin 2) := inferInstance by_cases hne : u.Nonempty · obtain ⟨a, ha⟩ := hne rw [Finset.card_eq_one] refine ⟨a, Finset.eq_singleton_iff_unique_mem.2 ⟨ha, fun b hb => ?_⟩⟩ by_contra hba have : (⊤ : SimpleGraph (Fin 2)).Adj b a := hba exact hu.1 hb ha hba this · rw [Finset.not_nonempty_iff_eq_empty] at hne subst hne have hv : (⊤ : SimpleGraph (Fin 2)).IsIndepSet (({v0} : Finset (Fin 2)) : Set (Fin 2)) := by simp have := hu.2 hv (Finset.empty_subset _) simp at this
The maximal independent sets s and t have equal cardinality, concluding the proof.
Applying the cardinality lemma from the previous step to both s and t gives |s| = 1 and |t| = 1, so |s| = |t|.
rw [hcard s hs, hcard t ht]
SimpleGraph.connected_top- The complete graph on any nonempty vertex set is connected.
SimpleGraph.diam_top- The diameter of the complete graph ⊤ on a nontrivial type is 1.
forall_power_well_covered_of_well_covered_diam_le_two- If a finite graph G is connected, has diameter at most 2, and is well-covered, then every positive power G^d (d ≥ 1) is well-covered.
Finset.card_eq_one- A finite set has cardinality 1 if and only if it is a singleton.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is empty.
Finset.empty_subset- The empty set is a subset of every finite set.
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.
/-- The complete graph K_2 is connected, has diameter 1, and has well-covered powers. -/theorem complete_graph_two_all_powers_well_covered : (SimpleGraph.completeGraph (Fin 2)).Connected ∧ (SimpleGraph.completeGraph (Fin 2)).diam = 1 ∧ ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (SimpleGraph.completeGraph (Fin 2)) d) := by have hconn : (SimpleGraph.completeGraph (Fin 2)).Connected := SimpleGraph.connected_top have hdiam : (SimpleGraph.completeGraph (Fin 2)).diam = 1 := by change (⊤ : SimpleGraph (Fin 2)).diam = 1 exact SimpleGraph.diam_top refine ⟨hconn, hdiam, ?_⟩ apply forall_power_well_covered_of_well_covered_diam_le_two · exact hconn · rw [hdiam] omega · change simple_graph_is_well_covered (⊤ : SimpleGraph (Fin 2)) intro s t hs ht have hcard : ∀ u : Finset (Fin 2), Maximal (fun (w : Finset (Fin 2)) => (⊤ : SimpleGraph (Fin 2)).IsIndepSet (w : Set (Fin 2))) u → u.card = 1 := by intro u hu obtain ⟨v0⟩ : Nonempty (Fin 2) := inferInstance by_cases hne : u.Nonempty · obtain ⟨a, ha⟩ := hne rw [Finset.card_eq_one] refine ⟨a, Finset.eq_singleton_iff_unique_mem.2 ⟨ha, fun b hb => ?_⟩⟩ by_contra hba have : (⊤ : SimpleGraph (Fin 2)).Adj b a := hba exact hu.1 hb ha hba this · rw [Finset.not_nonempty_iff_eq_empty] at hne subst hne have hv : (⊤ : SimpleGraph (Fin 2)).IsIndepSet (({v0} : Finset (Fin 2)) : Set (Fin 2)) := by simp have := hu.2 hv (Finset.empty_subset _) simp at this rw [hcard s hs, hcard t ht]