bot_isTwoKTwoFree
The empty graph on any vertex type is 2K₂-free.
Statement
theorem bot_isTwoKTwoFree (V : Type*) : IsTwoKTwoFree (⊥ : SimpleGraph V)
- Source
- arXiv:2611.17183, Definition 2.1
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- IsTwoKTwoFreeA simple graph G is 2K₂-free if for every pair of edges (a, b) and (c, d) in G, at least one of (a, c), (a, d), (b, c), or (b, d) is an…
- simple_graph_power_oneG^1 = G.
Read back from the Lean
For any type V, the empty simple graph on V (⊥ : SimpleGraph V) is IsTwoKTwoFree: for all vertices a, b, c, d : V, if a is adjacent to b in ⊥ and c is adjacent to d in ⊥, then a is adjacent to c, a is adjacent to d, b is adjacent to c, or b is adjacent to d in ⊥.
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 empty graph ⊥ contains no edges, so the defining condition of being 2K₂-free—that every pair of independent edges has a cross-edge between their endpoints—holds vacuously. The proof unfolds the definition of `IsTwoKTwoFree` and invokes the simplifier, which replaces adjacency in ⊥ with `False` and discharges the goal by propositional logic.
The empty graph ⊥ is 2K₂-free. automation
The tactic combinator `first` tries several proof attempts. The successful branch unfolds the definition of `IsTwoKTwoFree` using `simp only [IsTwoKTwoFree] at *`, which turns the goal into: for all vertices a, b, c, d, if ⊥.Adj a b and ⊥.Adj c d, then at least one cross-edge exists. Next, `simpa` simplifies the empty graph adjacency relation `⊥.Adj` to `False`. Since the premise `False` implies anything, propositional simplification reduces the goal to `True`, closing it without needing `simple_graph_power_one`.
uses
IsTwoKTwoFree,simple_graph_power_onetheorem bot_isTwoKTwoFree (V : Type*) : IsTwoKTwoFree (⊥ : SimpleGraph V) := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [IsTwoKTwoFree] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)
IsTwoKTwoFree- A graph is 2K₂-free if for all vertices a, b, c, d, whenever (a, b) and (c, d) are edges, at least one of (a, c), (a, d), (b, c), or (b, d) is also an edge.
simple_graph_power_one- The first graph power of any simple graph G is equal to G itself.
- The proof was generated by an automated search combinator (`first | ...`). Although `simple_graph_power_one` is passed to `simpa`, it is unused in the final proof: the simplifier reduces the goal on its own because adjacency in the empty graph (`⊥.Adj`) simplifies to `False`, making the implication vacuously true.
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 empty graph is 2K₂-free. -/theorem bot_isTwoKTwoFree (V : Type*) : IsTwoKTwoFree (⊥ : SimpleGraph V) := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [IsTwoKTwoFree] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)