b4_graph_adj
Sanity lemma: two distinct vertices in B_4(n) are adjacent if and only if they belong to the same block, or one is in block 0 and the other in block 1, or one in block 1 and the other in block 3, or one in block 2 and the other in block 3.
Statement
@[simp] theorem b4_graph_adj (n : Fin 4 → ℕ) (x y : Σ i : Fin 4, Fin (n i)) : (b4_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ (x.1 = 0 ∧ y.1 = 1) ∨ (x.1 = 1 ∧ y.1 = 0) ∨ (x.1 = 1 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 1) ∨ (x.1 = 2 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 2))
- Source
- arXiv:2610.21388, Section 2
- Verified
- 23 Oct 2026
- Axioms
propext- Built on 1
- b4_graphThe graph B_4(n_0, n_1, n_2, n_3) on the disjoint union of four complete blocks of sizes n_0, n_1, n_2, n_3, with edges between blocks 0…
- Used by 1
- b4_cliqueNumThe clique number of B_4(n_0, n_1, n_2, n_3) is max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
Read back from the Lean
For every function $n : \text{Fin } 4 \to \mathbb{N}$ and any two elements $x, y$ of the disjoint union $\sum_{i : \text{Fin } 4} \text{Fin}(n(i))$, $x$ and $y$ are adjacent in the simple graph b4_graph n if and only if $x \neq y$ and at least one of the following holds:
1. $x.1 = y.1$ (they belong to the same part),
2. $x.1 = 0$ and $y.1 = 1$,
3. $x.1 = 1$ and $y.1 = 0$,
4. $x.1 = 1$ and $y.1 = 3$,
5. $x.1 = 3$ and $y.1 = 1$,
6. $x.1 = 2$ and $y.1 = 3$, or
7. $x.1 = 3$ and $y.1 = 2$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Adjacency in the graph $B_4(n)$ is defined directly as the condition that two vertices are distinct and belong either to the same block or to adjacent blocks (specifically edges between blocks 0 and 1, 1 and 3, or 2 and 3). Because the statement of the lemma matches the definition of `b4_graph` identically, the equivalence holds by definitional reflexivity via `Iff.rfl`.
Adjacency in $B_4(n)$ is equivalent to the given condition by definition.
By definition of `b4_graph`, the adjacency relation `(b4_graph n).Adj x y` is literally defined to be the conjunction of $x \neq y$ and the disjunction of block-membership conditions. Therefore, both sides of the equivalence are syntactically identical after unfolding the definition, and the claim holds by reflexivity (`Iff.rfl`).
uses
Iff.rfl(x.1 = 1 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 1) ∨ (x.1 = 2 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 2)) := Iff.rfl
Iff.rfl- Logical equivalence is reflexive: any proposition is equivalent to itself.
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
/-- Sanity lemma: adjacency in B_4(n) unfolds to: distinct, and same block or one of the edges (0,1), (1,3), (2,3) between blocks. -/@[simp] theorem b4_graph_adj (n : Fin 4 → ℕ) (x y : Σ i : Fin 4, Fin (n i)) : (b4_graph n).Adj x y ↔ x ≠ y ∧ (x.1 = y.1 ∨ (x.1 = 0 ∧ y.1 = 1) ∨ (x.1 = 1 ∧ y.1 = 0) ∨ (x.1 = 1 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 1) ∨ (x.1 = 2 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 2)) := Iff.rfl