Proof of `Neighborhood covers from vertex orderings`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The cover of an ordering (Lemma 6.9 of Grohe–Kreutzer–Siebertz, the parametric core of their Theorem 6.2). For any ordering whose weak -reachability sets have at most elements, the fibers of weak -reachability form an -neighborhood cover of radius and degree at most .
Proof strategy
For the supplied ordering , let the cluster of be , the set of vertices from which is weakly -reachable.
The degree bound is the definition read backwards: the set of clusters containing is indexed by , which is itself, of size at most by hypothesis. The radius bound drops the minimality clause: a vertex in the cluster of reaches by a walk of length at most , which reversed puts it in the -ball of .
Covering is the only real argument. Given , let be a -minimal vertex of the -ball of , which is nonempty and finite. For in that ball, concatenate the reversed ball walk with the ball walk : a walk of length at most from to . Every vertex on it lies on one of the two halves, and cutting a walk of length at most at any of its vertices shows that vertex to be within distance of both endpoints — so the whole support stays inside the -ball of , where is -minimal. Hence is weakly -reachable from , i.e. lies in the cluster of .