AFTD Auto-Formalizing Theoretical Domains

b5_graph_adj

theoremverified

Sanity lemma: adjacency in B_5 unfolds to: distinct, and the same block or adjacent blocks of G_5.

Statement

@[simp] theorem b5_graph_adj (n : Fin 5 → ℕ) (x y : Σ i : Fin 5, Fin (n i)) :
    (b5_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ g5_adj x.1 y.1)
Source
sanity lemma for b5_graph
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • b5_graphThe graph B_5(n_1..n_5) of arXiv:2610.21388: each vertex i of G_5 is replaced by a clique of n_i vertices, and cliques of adjacent…
  • g5_adjG_5 on vertices r_1, r_2, w_1, w_2, r_3 (indices 0..4): edges r_1 r_2, w_1 w_2, r_2 w_2, and r_3 adjacent to all.
Used by 1
  • b5_cliqueNumω(B_5(n_0..n_4)) = n_4 + max(n_0 + n_1, n_1 + n_3, n_2 + n_3).

The proof, explained

The lemma unfolds the definition of adjacency in the graph B_5: two vertices are adjacent if and only if they are distinct and belong either to the same block or to adjacent blocks of G_5. Because this is the exact definition of `(b5_graph n).Adj`, the equivalence holds definitionally by reflexivity (`Iff.rfl`).

  1. Two vertices in B_5 are adjacent if and only if they are distinct and their blocks are either identical or adjacent in G_5.

    The adjacency relation of `b5_graph n` is defined directly as `fun x y => x ≠ y ∧ (x.1 = y.1 ∨ g5_adj x.1 y.1)`. Because the left-hand and right-hand sides of the equivalence are definitionally equal, the bi-implication is established by the reflexivity of logical equivalence (`Iff.rfl`).

    line 2

    uses Iff.rfl

        (b5_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ g5_adj x.1 y.1) := Iff.rfl
Iff.rfl
Every 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 b5_graph_adj (n : Fin 5 → ℕ) (x y : Σ i : Fin 5, Fin (n i)) :    (b5_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ g5_adj x.1 y.1) := Iff.rfl
See it in the graphDiscuss this resultChallenge it