three_graph_link_adj_iff
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
- three_graph_link_template_zero_adjIn the template, 1 and 4 are adjacent in the link of 0 (since {0, 1, 4} is an edge).
- bipartite_link_template_three_graph_links_colorable_twoEvery vertex link graph of the 9-vertex template 3-graph is bipartite (2-colorable).
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.
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).
uses
SimpleGraph.fromRel_adjsimp [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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]