simple_graph_triangle_cover_packing_gap_witness_graph_decidable
instance
Adjacency in the witness graph is decidable, so the finite computations can be run by decide.
Statement
instance simple_graph_triangle_cover_packing_gap_witness_graph_decidable : DecidableRel simple_graph_triangle_cover_packing_gap_witness_graph.Adj- Source
- step towards simple_graph_minimum_triangle_cover_outside_maximum_packing_support
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 2
- simple_graph_triangle_cover_packing_gap_deleted_edgesThe four edges deleted from K7 to build the witness graph: {0,1}, {1,2}, {1,3}, {3,4}.
- simple_graph_triangle_cover_packing_gap_witness_graphThe seven-vertex witness graph: K7 with the edges {0,1}, {1,2}, {1,3}, {3,4} deleted (17 edges, 19 triangles).
Lean source view module on GitHub
/-- Decidable adjacency for the witness graph. -/ instance simple_graph_triangle_cover_packing_gap_witness_graph_decidable : DecidableRel simple_graph_triangle_cover_packing_gap_witness_graph.Adj := fun a b => by show Decidable (a ≠ b ∧ Sym2.mk a b ∉ simple_graph_triangle_cover_packing_gap_deleted_edges) infer_instance