AFTD Auto-Formalizing Theoretical Domains

IsTwoKTwoFree

def

A 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 edge of G (that is, G contains no induced 2K₂, the disjoint union of two edges).

Statement

def IsTwoKTwoFree {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.17183, Section 3
Verified
14 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a type V and a simple graph G on V, IsTwoKTwoFree G is defined as the proposition that for all vertices a, b, c, d : V, if a is adjacent to b in G and c is adjacent to d in G, then at least one of the following holds: a is adjacent to c, a is adjacent to d, b is adjacent to c, or b is adjacent to d.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A simple graph is 2K₂-free if it contains no induced subgraph isomorphic to 2K₂ (two disjoint edges). -/
def IsTwoKTwoFree {V : Type*} (G : SimpleGraph V) : Prop := ∀ a b c d : V, G.Adj a b → G.Adj c d →
    G.Adj a c ∨ G.Adj a d ∨ G.Adj b c ∨ G.Adj b d
See it in the graphDiscuss this resultChallenge it