AFTD Auto-Formalizing Theoretical Domains

g5_adj_symm

theoremverified

Sanity lemma: the adjacency of G_5 is symmetric.

Statement

theorem g5_adj_symm (i j : Fin 5) (h : g5_adj i j) : g5_adj j i
Source
sanity lemma for g5_adj (arXiv:2610.21388, Def. 2.1, t = 5)
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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_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…

The proof, explained

The theorem states that the adjacency relation of the 5-vertex graph $G_5$ is symmetric. Because the vertex set $\text{Fin } 5$ has only 5 elements, the proof proceeds by exhaustive case analysis over all 25 pairs of vertices $(i, j)$. In each case, automated simplification unfolds the definition of `g5_adj` and evaluates the finite set membership and disjunctions to verify symmetry.

  1. For all $i, j \in \text{Fin } 5$, if $g5\_adj(i, j)$ holds, then $g5\_adj(j, i)$ holds. automation

    We perform an exhaustive case analysis over all 25 possible pairs of vertices $(i, j) \in \text{Fin } 5 \times \text{Fin } 5$ using `fin_cases`. For each pair, the definition of `g5_adj` is unfolded and evaluated by `simp_all`: when $i = j$, the hypothesis $i \neq j$ is contradictory; when $i \neq j$, the condition $i = 4 \lor j = 4 \lor (i, j) \in \dots$ is symmetric in $i$ and $j$, so the goal $g5\_adj(j, i)$ simplifies to true given the hypothesis $g5\_adj(i, j)$.

    line 2

    uses g5_adj

      fin_cases i <;> fin_cases j <;> simp_all [g5_adj]
g5_adj
the adjacency relation on Fin 5, which holds when $i \neq j$ and either $i = 4$, $j = 4$, or $(i, j)$ is one of the symmetric pairs $(0, 1), (1, 0), (1, 3), (3, 1), (2, 3), (3, 2)$

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem g5_adj_symm (i j : Fin 5) (h : g5_adj i j) : g5_adj j i := by  fin_cases i <;> fin_cases j <;> simp_all [g5_adj]
See it in the graphDiscuss this resultChallenge it