k99_join_compl_k2_not_adj_join_vertices
In the complete bipartite join graph K_{9,9} ∨ Compl(K_2), the two vertices in the independent set of size 2 are not adjacent to each other.
Statement
theorem k99_join_compl_k2_not_adj_join_vertices (v1 v2 : Fin 2) :
¬ k99_join_compl_k2.Adj (Sum.inr (Sum.inr v1)) (Sum.inr (Sum.inr v2))- Source
- arXiv:2611.09347 Definition 1 -- A Structural Lower Bound for the Ramsey Number of the Petersen Graph
- Verified
- 10 Nov 2026
- Axioms
propext- Built on 2
- k99_join_compl_k2The complete bipartite join graph K_{9,9} ∨ Compl(K_2) has vertex set Fin 9 ⊕ Fin 9 ⊕ Fin 2, where the first two parts of size 9 induce a…
- simple_graph_pendant_triple_expand_leaf_adjEach added leaf is adjacent exactly to its corresponding fresh internal path vertex.
Read back from the Lean
For all $v_1, v_2 : \mathrm{Fin}(2)$, the vertices $\mathrm{Sum.inr}(\mathrm{Sum.inr}(v_1))$ and $\mathrm{Sum.inr}(\mathrm{Sum.inr}(v_2))$ are not adjacent in the simple graph k99_join_compl_k2.
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
The theorem states that the two vertices in the independent set of size 2 in the graph $K_{9,9} \lor \overline{K_2}$ are not adjacent. By definition of $K_{9,9} \lor \overline{K_2}$, edges only exist between the bipartite parts and between the bipartite graph and the size-2 set, so the adjacency relation between two vertices in the size-2 set evaluates to false. Unfolding the definition reduces the goal to $\neg \text{False}$, which holds trivially.
The two vertices in the size-2 component of $K_{9,9} \lor \overline{K_2}$ are not adjacent.
Unfolding the definition of adjacency in `k99_join_compl_k2`, any pair of vertices belonging to the final component $\text{Fin } 2$ (represented as `Sum.inr (Sum.inr _)`) falls through to the catch-all case `_ => False`. Consequently, the adjacency condition evaluates to $\text{False}$, reducing the goal to $\neg \text{False}$, which simplifies immediately to $\text{True}$.
uses
k99_join_compl_k2,simple_graph_pendant_triple_expand_leaf_adj¬ k99_join_compl_k2.Adj (Sum.inr (Sum.inr v1)) (Sum.inr (Sum.inr v2)) := by first | exact simple_graph_pendant_triple_expand_leaf_adj | (apply simple_graph_pendant_triple_expand_leaf_adj <;> assumption) | (apply simple_graph_pendant_triple_expand_leaf_adj <;> simp_all) | simpa using simple_graph_pendant_triple_expand_leaf_adj | (simp only [k99_join_compl_k2] at *; first | exact simple_graph_pendant_triple_expand_leaf_adj | (apply simple_graph_pendant_triple_expand_leaf_adj <;> assumption) | (apply simple_graph_pendant_triple_expand_leaf_adj <;> simp_all) | simpa using simple_graph_pendant_triple_expand_leaf_adj)
k99_join_compl_k2- The definition of the graph $K_{9,9} \lor \overline{K_2}$ on vertices $(\text{Fin } 9 \oplus \text{Fin } 9) \oplus \text{Fin } 2$, specifying that edges exist between the two size-9 bipartite classes and between each size-9 class and the size-2 class, but no edges exist within the size-2 class.
simple_graph_pendant_triple_expand_leaf_adj- In the pendant triple expansion of a graph $G$, a vertex $p$ is adjacent to the leaf vertex $i + 3$ if and only if $p$ is the attachment vertex $i$. (Syntactically present in the tactic script, but not mathematically used in the proof.)
- The proof script was generated by an automated proof search (`first | ...`) and references the lemma `simple_graph_pendant_triple_expand_leaf_adj`, which is completely unrelated to this graph. In reality, only expanding the definition of `k99_join_compl_k2` (which reduces the adjacency to `False`) and simplifying `¬False` to `True` are used to close the goal.
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.
/-- The two join vertices in K_{9,9} ∨ K_2ᶜ are not adjacent. -/theorem k99_join_compl_k2_not_adj_join_vertices (v1 v2 : Fin 2) : ¬ k99_join_compl_k2.Adj (Sum.inr (Sum.inr v1)) (Sum.inr (Sum.inr v2)) := by first | exact simple_graph_pendant_triple_expand_leaf_adj | (apply simple_graph_pendant_triple_expand_leaf_adj <;> assumption) | (apply simple_graph_pendant_triple_expand_leaf_adj <;> simp_all) | simpa using simple_graph_pendant_triple_expand_leaf_adj | (simp only [k99_join_compl_k2] at *; first | exact simple_graph_pendant_triple_expand_leaf_adj | (apply simple_graph_pendant_triple_expand_leaf_adj <;> assumption) | (apply simple_graph_pendant_triple_expand_leaf_adj <;> simp_all) | simpa using simple_graph_pendant_triple_expand_leaf_adj)