dist_two_graph
def
The graph on V in which two distinct vertices are adjacent when they are adjacent in G or have a common neighbour in G; its neighbour sets are the sets of vertices at distance 1 or 2 in G.
Statement
@[reducible] def dist_two_graph {V : Type} (G : SimpleGraph V) : SimpleGraph V
- Source
- step towards sparse_strong_odd_five_list_coloring
- Verified
- 27 Oct 2026
- Axioms
- none listed
Lean source view module on GitHub
/-- The distance-≤2 graph (square) of `G`: `a` and `b` are adjacent when they are distinct and joined by a walk of length 1 or 2 in `G`. A proper colouring of this graph assigns distinct colours to any two neighbours of a common vertex, which is exactly what a strong odd colouring of `G` needs. -/ @[reducible] def dist_two_graph {V : Type} (G : SimpleGraph V) : SimpleGraph V := SimpleGraph.fromRel fun a b => G.Adj a b ∨ ∃ c, G.Adj a c ∧ G.Adj c b