balanced_complete_multipartite_graph_adj
In balanced_complete_multipartite_graph r n, u and v are adjacent iff u / n ≠ v / n.
Statement
theorem balanced_complete_multipartite_graph_adj (r n : ℕ) (u v : Fin (r * n)) :
(balanced_complete_multipartite_graph r n).Adj u v ↔ (u : ℕ) / n ≠ (v : ℕ) / n- Source
- sanity lemma for balanced_complete_multipartite_graph (OP-546)
- Verified
- 27 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- balanced_complete_multipartite_graphFor natural numbers r and n, balanced_complete_multipartite_graph r n is the simple graph on Fin (r * n) in which u and v are adjacent…
The proof, explained
By definition, the balanced complete multipartite graph has vertex set Fin (r * n), with two vertices u and v being adjacent precisely when their integer quotients by n are distinct (that is, they lie in different partite sets). Because the adjacency relation is defined to be this exact inequality, the left- and right-hand sides of the equivalence are definitionally equal. The theorem follows immediately by reflexivity of the logical equivalence.
In the balanced complete multipartite graph with parameters r and n, vertices u and v are adjacent if and only if u / n ≠ v / n.
By the definition of `balanced_complete_multipartite_graph`, the adjacency relation `Adj u v` is defined directly as `(u : ℕ) / n ≠ (v : ℕ) / n`. Because both sides of the bi-implication are definitionally identical, the equivalence holds by reflexivity (`Iff.rfl`).
uses
Iff.rfl(balanced_complete_multipartite_graph r n).Adj u v ↔ (u : ℕ) / n ≠ (v : ℕ) / n := Iff.rfl
Iff.rfl- Every proposition is equivalent to itself: for any proposition P, P ↔ P.
- The equivalence is true definitionally from the construction of `balanced_complete_multipartite_graph`, so the proof requires only reflexivity.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem balanced_complete_multipartite_graph_adj (r n : ℕ) (u v : Fin (r * n)) : (balanced_complete_multipartite_graph r n).Adj u v ↔ (u : ℕ) / n ≠ (v : ℕ) / n := Iff.rfl