AFTD Auto-Formalizing Theoretical Domains

bot_isTwoKTwoFree

theoremverified

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.

  1. 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`.

    line 2

    uses IsTwoKTwoFree, simple_graph_power_one

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

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