AFTD Auto-Formalizing Theoretical Domains

balanced_complete_multipartite_graph_adj

theoremverified

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

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.

  1. 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`).

    line 2

    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.

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