simple_graph_rich_witness_graph
def
The graph on the edges of G joining adjacent edges and distinct pairs sharing a neighboring edge from R.
Statement
def simple_graph_rich_witness_graph {V : Type*} (G : SimpleGraph V) (R : Set G.edgeSet) : SimpleGraph G.edgeSet where Adj e f
- Defined in
- arXiv:2610.16446, Section 2, the calligraphic graph defined before Lemma 3; simple-graph specialization, used for OP-309.
- Verified
- 24 Oct 2026
- Axioms
- none listed
- Used by 3
- simple_graph_rich_neighbor_coloring_iff_witness_graphG has a rich-neighbor coloring with palette alpha exactly when some R totally dominates the non-isolated vertices of the line graph and…
- simple_graph_rich_witness_graph_coloring_iffColorability of the prescribed-witness graph is equivalent to a proper edge-coloring of G in which every prescribed edge of R is rich.
- simple_graph_rich_witness_graph_cubic_triangle_free_neighborsIn a finite triangle-free cubic graph, every vertex of a prescribed-witness graph has at least six neighbors whenever R totally dominates…
Lean source view module on GitHub
def simple_graph_rich_witness_graph {V : Type*} (G : SimpleGraph V) (R : Set G.edgeSet) : SimpleGraph G.edgeSet where Adj e f := e ≠ f ∧ (G.lineGraph.Adj e f ∨ ∃ r ∈ R, G.lineGraph.Adj r e ∧ G.lineGraph.Adj r f) symm := ⟨by intro e f h refine ⟨h.1.symm, ?_⟩ rcases h.2 with h | ⟨r, hr, he, hf⟩ · exact Or.inl h.symm · exact Or.inr ⟨r, hr, hf, he⟩⟩ loopless := ⟨by intro e h; exact h.1 rfl⟩