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
- maxcut_defect_one_coloring_without_optimal_defect_oneThe eight-vertex graph has a defect-one three-coloring but no optimal three-coloring has defect one.
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)])