simple_graph_equivalence_covering_number_top
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
- simple_graph_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- simple_graph_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- Used by 1
- simple_graph_equivalence_covering_number_cycle_power_of_leIf 2 ≤ n ≤ 2k + 1 then every two vertices of C_n are at cyclic distance at most k, so C_n^k = K_n and eq(C_n^k) = 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.
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.
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⟩⟩
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`.
uses
le_antisymm,Nat.sInf_leapply le_antisymm · exact Nat.sInf_le h1
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.
uses
le_csInf· refine le_csInf ⟨1, h1⟩ fun t ht => ?_
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`.
uses
exists_pair_ne,Nat.one_le_iff_ne_zero.mprobtain ⟨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
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.
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