AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_top

theoremverified

Sanity check: a complete graph with at least two vertices has equivalence covering number 1.

Statement

theorem simple_graph_equivalence_covering_number_top {V : Type*} [Nontrivial V] :
    simple_graph_equivalence_covering_number (⊤ : SimpleGraph V) = 1
Source
Sanity lemma for eq(G), arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs) (Theorem 1.2 uses eq(K_n) = 1).
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

An equivalence cover of a simple graph is a family of equivalence relations whose equivalence classes are cliques, covering all edges of the graph, and the equivalence covering number is the minimum size of such a cover. For the complete graph on a nontrivial vertex set, a single equivalence relation with one equivalence class covers all pairs of vertices, showing the covering number is at most 1. Conversely, because the vertex set has at least two distinct vertices forming an edge, any valid cover must provide at least one index to cover that edge, showing the covering number is at least 1.

  1. The complete graph $\\top$ has an equivalence cover of size $1$.

    Because $V$ is nontrivial, it is nonempty; let $x \\in V$ be any vertex. We define a single coloring function $c : \\operatorname{Fin} 1 \\to V \\to V$ that assigns the constant value $x$ to every vertex. Any two distinct vertices $u \\ne v$ are adjacent in $\\top$ by definition, so the condition that monochromatic pairs form cliques holds trivially. Furthermore, under the unique index $0$, any pair of vertices shares the same color $x$, so every edge is covered.

    lines 3–5

      have h1 : simple_graph_has_equivalence_cover (⊤ : SimpleGraph V) 1 := by
        obtain ⟨x⟩ := (inferInstance : Nonempty V)
        exact ⟨fun _ _ => x, fun _ _ _ huv _ => huv, fun _ _ _ => ⟨0, rfl⟩⟩
  2. The covering number of $\\top$ is at most $1$.

    By antisymmetry of the order (`le_antisymm`), it suffices to show both $\\le 1$ and $\\ge 1$. Since $1$ belongs to the set of valid cover sizes by the previous step, the infimum of this set is at most $1$ by `Nat.sInf_le`.

    lines 6–7

    uses le_antisymm, Nat.sInf_le

      apply le_antisymm
      · exact Nat.sInf_le h1
  3. To show the covering number is at least $1$, it suffices to show that any valid cover size $t$ satisfies $1 \\le t$.

    Because the set of cover sizes is nonempty (it contains $1$), `le_csInf` implies that any lower bound on all valid cover sizes is a lower bound on their infimum.

    line 8

    uses le_csInf

      · refine le_csInf ⟨1, h1⟩ fun t ht => ?_
  4. Every valid cover size $t$ is at least $1$.

    Given an equivalence cover $c$ of size $t$, nontriviality of $V$ guarantees two distinct vertices $x \\ne y$ (`exists_pair_ne`). Distinct vertices are adjacent in $\\top$, so the covering property yields an index $s \\in \\operatorname{Fin} t$ where $x$ and $y$ are identified. The existence of this index $s$ implies that $t$ cannot be $0$ (which would make $\\operatorname{Fin} 0$ empty, contradicting the existence of $s$), and therefore $1 \\le t$ by `Nat.one_le_iff_ne_zero.mpr`.

    lines 9–12

    uses exists_pair_ne, Nat.one_le_iff_ne_zero.mpr

        obtain ⟨c, -, hcov⟩ := ht
        obtain ⟨x, y, hxy⟩ := exists_pair_ne V
        obtain ⟨s, -⟩ := hcov x y hxy
        exact Nat.one_le_iff_ne_zero.mpr fun h => by subst h; exact s.elim0
le_antisymm
In a partial order, if $a \\le b$ and $b \\le a$, then $a = b$.
Nat.sInf_le
If a natural number $m$ belongs to a set $s \\subseteq \\mathbb{N}$, then $\\operatorname{sInf} s \\le m$.
le_csInf
In a conditionally complete lattice, if a set $s$ is nonempty and bounded below by $a$ (i.e., $a \\le b$ for all $b \\in s$), then $a \\le \\operatorname{sInf} s$.
exists_pair_ne
In any nontrivial type, there exist two distinct elements.
Nat.one_le_iff_ne_zero.mpr
A natural number $n$ satisfies $1 \\le n$ whenever $n \\ne 0$.

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

theorem simple_graph_equivalence_covering_number_top {V : Type*} [Nontrivial V] :    simple_graph_equivalence_covering_number (⊤ : SimpleGraph V) = 1 := by  have h1 : simple_graph_has_equivalence_cover (⊤ : SimpleGraph V) 1 := by    obtain ⟨x⟩ := (inferInstance : Nonempty V)    exact ⟨fun _ _ => x, fun _ _ _ huv _ => huv, fun _ _ _ => ⟨0, rfl⟩⟩  apply le_antisymm  · exact Nat.sInf_le h1  · refine le_csInf ⟨1, h1⟩ fun t ht => ?_    obtain ⟨c, -, hcov⟩ := ht    obtain ⟨x, y, hxy⟩ := exists_pair_ne V    obtain ⟨s, -⟩ := hcov x y hxy    exact Nat.one_le_iff_ne_zero.mpr fun h => by subst h; exact s.elim0
See it in the graphDiscuss this resultChallenge it