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
- bot_isTwoKTwoFreeThe empty graph on any vertex type is 2K₂-free.
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