AFTD Auto-Formalizing Theoretical Domains

k99_join_compl_k2_not_adj_join_vertices

theoremverified

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

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.

  1. 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}$.

    line 3

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

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

/-- 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)
See it in the graphDiscuss this resultChallenge it