AFTD Auto-Formalizing Theoretical Domains

b3_graph_adj

theoremverified

Sanity lemma: adjacency in B_3(n_0,n_1,n_2) unfolds to: distinct, and same block or one endpoint in block 2.

Statement

@[simp] theorem b3_graph_adj (n : Fin 3 → ℕ) (x y : Σ i : Fin 3, Fin (n i)) :
    (b3_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ x.1 = 2 ∨ y.1 = 2)
Source
sanity lemma for b3_graph (arXiv:2610.21388 Theorem 3.1)
Verified
18 Oct 2026
Axioms
propext
Built on 1
  • b3_graphThe graph B_3(n_0, n_1, n_2) on the disjoint union of blocks of sizes n_0, n_1, n_2: two distinct vertices are adjacent iff they lie in…
Used by 2
  • b3_cliqueNumThe clique number of B_3(n_0, n_1, n_2) is max(n_0 + n_2, n_1 + n_2).
  • b3_adjMatrix_trace_sqFor B_3(n_0,n_1,n_2) with adjacency matrix A: tr(A^2) = tr(M^2) + (n - 3). Since tr(A^2) is the sum of the squares of all adjacency…

The proof, explained

The statement holds immediately by definition. The graph `b3_graph n` is defined with the given adjacency condition, so both sides of the bi-implication are definitionally identical and the result follows by the reflexivity of logical equivalence.

  1. The adjacency relation (b3_graph n).Adj x y is equivalent to x ≠ y ∧ (x.1 = y.1 ∨ x.1 = 2 ∨ y.1 = 2).

    By definition of `b3_graph`, its adjacency relation is literally `fun x y => x ≠ y ∧ (x.1 = y.1 ∨ x.1 = 2 ∨ y.1 = 2)`. Because the left-hand side reduces to the right-hand side definitionally, the bi-implication holds by reflexivity of `↔` (Iff.rfl).

    line 2

    uses Iff.rfl

        (b3_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ x.1 = 2 ∨ y.1 = 2) := Iff.rfl
Iff.rfl
A proposition is equivalent to itself (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

@[simp] theorem b3_graph_adj (n : Fin 3 → ℕ) (x y : Σ i : Fin 3, Fin (n i)) :    (b3_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ x.1 = 2 ∨ y.1 = 2) := Iff.rfl
See it in the graphDiscuss this resultChallenge it