simple_graph_edge_is_rich
def
In an edge colouring c, an edge e is rich if all edges adjacent to e receive pairwise distinct colours.
Statement
def simple_graph_edge_is_rich {V α : Type*} (G : SimpleGraph V) (c : G.edgeSet → α) (e : G.edgeSet) : Prop
- Defined in
- arXiv:2610.21868 (Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching), Sec. 1 (definition of a rich edge).
- Verified
- 16 Oct 2026
- Axioms
- none listed
- Used by 10
- subcubic_isAcyclic_exists_strong_five_edge_coloringEvery finite simple graph of maximum degree at most 3 that is acyclic admits a strong 5-edge-coloring (where all edges are rich).
- simple_graph_rich_neighbor_coloring_of_edge_familyAn indexed family of non-loop edges with colors yields a rich-neighbor coloring of its edge-family graph whenever properness and a…
- subcubic_rich_neighbor_five_isolated_vertex_extendIf v is an isolated vertex of the finite simple graph G and the induced subgraph of G on the vertices other than v admits a rich-neighbor…
- subcubic_isAcyclic_exists_rich_neighbor_five_coloringEvery subcubic acyclic finite simple graph admits a rich-neighbor 5-edge-colouring.
- simple_graph_is_rich_neighbor_coloring_of_forall_richA proper edge colouring in which every edge is rich (for instance a strong edge colouring) is a rich-neighbor edge colouring.
- simple_graph_strong_five_edge_coloring_extend_leaf_of_ncardGiven a leaf edge e of G with at most 4 other edges within distance 2 of e in the line graph (counted with Set.ncard), any strong…
- 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_is_rich_neighbor_coloringA proper edge colouring is a rich-neighbor edge colouring if every non-isolated edge (one with at least one adjacent edge) is adjacent to…
- 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.
- cyclic_four_block_graph_exists_rich_neighbor_five_coloringFor every m>=0, cyclic_four_block_graph m, on 4(2m+5) vertices, admits a rich-neighbor five-edge-coloring.
Lean source view module on GitHub
/-- `e` is rich for `c`: the edges adjacent to `e` have pairwise distinct colours. -/ def simple_graph_edge_is_rich {V α : Type*} (G : SimpleGraph V) (c : G.edgeSet → α) (e : G.edgeSet) : Prop := ∀ f g : G.edgeSet, G.lineGraph.Adj e f → G.lineGraph.Adj e g → f ≠ g → c f ≠ c g