AFTD Auto-Formalizing Theoretical Domains

complete_graph_two_all_powers_well_covered

theoremverified

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
Used by 1

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.

  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.

    lines 6–9

    uses SimpleGraph.connected_top, SimpleGraph.diam_top

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

    lines 10–14

    uses forall_power_well_covered_of_well_covered_diam_le_two

      refine ⟨hconn, hdiam, ?_⟩
      apply forall_power_well_covered_of_well_covered_diam_le_two
      · exact hconn
      · rw [hdiam]
        omega
  3. 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|.

    lines 15–16

      · change simple_graph_is_well_covered (⊤ : SimpleGraph (Fin 2))
        intro s t hs ht
  4. 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.

    lines 17–31

    uses Finset.card_eq_one, Finset.not_nonempty_iff_eq_empty, Finset.empty_subset

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

    line 32

        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

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