AFTD Auto-Formalizing Theoretical Domains

three_graph_link_adj_iff

theoremverified

In 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.

Statement

theorem three_graph_link_adj_iff {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (i j k : V) :
    (three_graph_link F i).Adj j k ↔ j ≠ k ∧ (({i, j, k} : Finset V) ∈ F ∨ ({i, k, j} : Finset V) ∈ F)
Source
Sanity check of the definitions of arXiv:2610.11642 (A counterexample to the bipartite-link conjecture for 3-graphs). Unfolds the link graph.
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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.
Used by 2

The proof, explained

The link graph of a vertex i in a 3-uniform hypergraph F is defined as the simple graph induced by the relation {i, j, k} ∈ F. By SimpleGraph.fromRel_adj, two vertices are adjacent in such a graph if and only if they are distinct and the relation holds in either order. Unfolding the definition and applying this characterisation proves the equivalence in a single step.

  1. Vertices j and k are adjacent in the link graph of i if and only if j ≠ k and either {i, j, k} ∈ F or {i, k, j} ∈ F.

    By definition, `three_graph_link F i` is `SimpleGraph.fromRel r` for the relation r(j, k) defined by {i, j, k} ∈ F. The lemma `SimpleGraph.fromRel_adj` states that vertices j and k are adjacent in `SimpleGraph.fromRel r` if and only if j ≠ k and (r(j, k) ∨ r(k, j)). Unfolding the definition of `three_graph_link` and rewriting with `SimpleGraph.fromRel_adj` reduces the adjacency condition directly to j ≠ k ∧ ({i, j, k} ∈ F ∨ {i, k, j} ∈ F).

    line 3

    uses SimpleGraph.fromRel_adj

      simp [three_graph_link, SimpleGraph.fromRel_adj]
SimpleGraph.fromRel_adj
In the simple graph constructed from a binary relation r, two vertices v and w are adjacent if and only if v ≠ w and either r v w or r w v holds.

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_adj_iff {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (i j k : V) :    (three_graph_link F i).Adj j k ↔ j ≠ k ∧ (({i, j, k} : Finset V) ∈ F ∨ ({i, k, j} : Finset V) ∈ F) := by  simp [three_graph_link, SimpleGraph.fromRel_adj]
See it in the graphDiscuss this resultChallenge it