AFTD Auto-Formalizing Theoretical Domains

three_graph_link_template_zero_adj

theoremverified

In the template, 1 and 4 are adjacent in the link of 0 (since {0, 1, 4} is an edge).

Statement

theorem three_graph_link_template_zero_adj :
    (three_graph_link bipartite_link_template_three_graph 0).Adj 1 4
Source
Sanity check of the definitions of arXiv:2610.11642 (A counterexample to the bipartite-link conjecture for 3-graphs).
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • three_graph_linkThe link graph of a vertex i in a 3-uniform hypergraph F: two distinct vertices j, k are adjacent iff {i, j, k} is an edge of F.
  • bipartite_link_template_three_graphThe 9-vertex template 3-graph on {0, …, 8} with the 24 triples listed in (2.1).
  • three_graph_link_adj_iffIn the link graph of i, j and k are adjacent iff they are distinct and {i, j, k} (in either order of j, k) is an edge.

The proof, explained

To establish that vertices 1 and 4 are adjacent in the link graph of vertex 0 in the hypergraph template, the proof rewrites the adjacency condition into a membership check. By `three_graph_link_adj_iff`, this holds if and only if $1 \ne 4$ and the triple $\{0, 1, 4\}$ is an edge in the hypergraph. The claim is then closed by computational evaluation (`decide`), inspecting the explicit list of hyperedges.

  1. 1 and 4 are adjacent in the link graph of vertex 0. automation

    By `three_graph_link_adj_iff`, two vertices $j$ and $k$ are adjacent in the link graph of $i$ if and only if $j \ne k$ and the hyperedge $\{i, j, k\}$ (or $\{i, k, j\}$) belongs to the hypergraph. For $i = 0$, $j = 1$, and $k = 4$, this reduces to verifying $1 \ne 4$ and that $\{0, 1, 4\}$ is an element of `bipartite_link_template_three_graph`. Because the template is defined as an explicit finite set of finite sets over $\mathrm{Fin}\;9$, this Boolean condition is verified by direct computation (`decide`).

    line 3

    uses three_graph_link_adj_iff

      rw [three_graph_link_adj_iff]; decide
three_graph_link_adj_iff
Two vertices $j$ and $k$ are adjacent in the link graph of vertex $i$ in a 3-uniform hypergraph $F$ if and only if $j \ne k$ and either $\{i, j, k\} \in F$ or $\{i, k, j\} \in F$.

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 three_graph_link_template_zero_adj :    (three_graph_link bipartite_link_template_three_graph 0).Adj 1 4 := by  rw [three_graph_link_adj_iff]; decide
See it in the graphDiscuss this resultChallenge it