AFTD Auto-Formalizing Theoretical Domains

maxcut_defect_one_nonoptimal_graph

def

An eight-vertex graph admitting a defect-one three-coloring although none of its optimal three-colorings is defect one.

Statement

def maxcut_defect_one_nonoptimal_graph : SimpleGraph (Fin 8)
Source
Graph found and independently verified in experiments 16395 and 16399.
Verified
06 Nov 2026
Axioms
none listed
Used by 1

Lean source view module on GitHub

def maxcut_defect_one_nonoptimal_graph : SimpleGraph (Fin 8) := SimpleGraph.fromRel (fun u v : Fin 8 => (u.val, v.val) ∈ [(0, 1), (0, 3), (0, 4), (0, 6), (0, 7), (1, 2), (1, 5), (1, 6), (1, 7), (2, 3), (2, 5), (2, 6), (2, 7), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (6, 7)])
See it in the graphDiscuss this resultChallenge it