How rigid is maximum cardinality search? Stability and locality of MCS orderings under edge updates, verified in Lean
Md Thoriqul Islam Thonmay, Gregory Morse
cs.DS
Nov 13, 2026 · v1
cs.LO
TL;DR
Lean 4/Mathlib proofs of MCS ordering stability, single-edge update locality, obstructions, and refinement of a boolean-adjacency executable, re-checked by external kernels.
Abstract
For which sets F of edge modifications do a graph G and the modified graph share a maximum cardinality search (MCS) ordering? We prove that they do whenever, along every proper common MCS prefix, each unchosen vertex's neighbour count in the second graph exceeds its count in the first by zero or one. In particular, inserting or deleting any matching, or flipping a single edge, preserves a common ordering, and under the same hypothesis every common MCS prefix extends to a full common ordering without backtracking. Neither part of the hypothesis can simply be dropped: inserting a triangle, a P_4 or a 2P_3 shows that the +1 bound cannot be relaxed to +2, and a disjoint mixed insert/delete pair shows that the one-directional condition is needed. For the canonical ordering (smallest-index tie-breaking) under a single-edge update, an insertion can first change the ordering only strictly between the endpoints' positions, and a deletion only at the later endpoint; when no break fires, the ordering is unchanged. A boolean-adjacency executable refines the abstract probe-then-repair update. All of these results, including the four obstructions, are proved in Lean 4 over Mathlib, re-checked by independent kernel checkers, and registered in the Palomar registry. On paper we further show that the first break of an insertion is located in O((deg(v)+1) log n) time, independent of the window length. We claim no worst-case asymptotic speedup over recomputation.
Problem
The paper asks when a graph and an edge-modified version of it share a maximum cardinality search (MCS) ordering. It also asks where a single-edge update can first disturb the canonical (smallest-index tie-break) MCS ordering.
Approach
A stability theorem gives a sufficient condition: along every proper common MCS prefix, each unchosen vertex's neighbour count rises by zero or one. Certified obstructions (triangle, P_4, 2P_3, mixed insert/delete pair) show the condition cannot be relaxed. A probe-then-repair update is analysed for locality, and a boolean-adjacency executable is proved to refine it, with probe/pick counts along its control flow. Everything except the sublinear probe bound is proved in Lean 4 over Mathlib, audited to the standard axioms, re-checked by nanoda and con-ron, and registered in the Palomar registry.
Results
Inserting or deleting any matching, or flipping a single edge, preserves a common ordering, and common prefixes extend to full common orderings without backtracking. An insertion can first change the canonical ordering only strictly between the endpoints' positions, and a deletion only at the later endpoint. The update returns exactly the from-scratch ordering, and a paper-only proof locates the first insertion break in O((deg(v)+1) log n) time. No worst-case asymptotic speedup over recomputation is claimed.
| Category | Count | Section |
|---|
| update correctness | 5 | 4 |
| locality | 6 | 4 |
| probe/pick count | 6 | 7 |
| stability (matching, flip, prefix extension) | 5 | 3 |
| certified obstructions | 4 | 3 |
Comparator theorems by category (41 total; partial)