WorksComputer Science
How rigid is maximum cardinality search? Stability and locality of MCS orderings under edge updates, verified in Lean
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.
Introduction
A maximum cardinality search (MCS) numbers the vertices of a graph one at a time, always choosing a vertex with the most already-chosen neighbours. Tarjan and Yannakakis [16] introduced it as a simplification of the lexicographic breadth-first search (LexBFS) of Rose, Tarjan and Lueker [14]: LexBFS compares the sets of chosen neighbours lexicographically, MCS compares only their sizes. On chordal graphs, the reverse of an MCS ordering is a perfect elimination ordering [16], as Rose, Tarjan and Lueker showed for LexBFS [14]; such orderings are the standard tool for recognizing chordal graphs. Even on chordal graphs, the two ordering families are incomparable [6]. Tarjan and Yannakakis number the vertices from down to 1 and prescribe no tie-break; we number forward and break ties by smallest index throughout. Our question is dynamic: given an MCS ordering of a graph, how much of it must change when one edge is inserted or deleted?
The answer is structural, with one asymptotic result, the probe below. We make no worst-case asymptotic separation claim. In our unit-cost model an update costs at most units for an insertion and for a deletion, the same order as recomputing from scratch, and the static MCS of Tarjan and Yannakakis already runs in linear time. Because the update provably returns the from-scratch canonical ordering, our contribution is not a faster maintenance algorithm but, to our knowledge, the first locality analysis of MCS orderings under edge updates and the first machine-checked incremental repair of them (§ 9 records the survey behind this claim). What we prove comes in four parts. First, a stability theorem with obstructions (§ 3) that locates where two graphs stop sharing an MCS ordering. Second, the locality of a single-edge update (§ 4): the open window, or for a deletion the single position, where an update can first disturb the ordering. Third, a sublinear first-break probe (§ 5): the first break of an insertion is located in time, independent of the window length, so a no-change update can be certified in time for sparse endpoints. Fourth, a verified executable (§ 6) with a probe/pick count along its real control flow (§ 7). Every theorem except the probe bound is proved in Lean 4 and re-checked by an independent external kernel checker. The probe bound (Theorem 13) is proved on paper: its plateau bound is machine-checked, and the data-structure argument is on paper. Statements reported as computer-search results (minimal obstruction sizes, patterns that never failed up to a stated ) hold only for the sizes searched and are not theorems. § 8 describes the artifact.
Contributions
Stability theorem and obstructions. Write for the set of MCS orderings under arbitrary tie-breaking. For which edge-modification sets is ? The intersection is nonempty whenever, along every proper common MCS prefix, each unchosen vertex’s count in is at least its count in and at most one more. That covers every insertion-only or deletion-only matching and every single-edge flip. The hypotheses cannot be relaxed: a triangle, a , a and a disjoint mixed pair each leave no common ordering. An online corollary (
common_order_extends_prefix) ties the set-valued theory to the constructive update: under the same hypothesis, any common MCS prefix extends to a full common ordering without backtracking.
Locality. After a single-edge insertion, the ordering can first change only inside the open positional window between the two endpoints; after a deletion, only at the later endpoint’s position. When no break fires, the ordering is literally unchanged, not merely still valid.
A sublinear first-break probe. Per-value search trees over the per-step data locate the first break of an insertion, or certify that there is none, in time, independent of the window length, and survive a no-break insertion at cost. That beats the naive scan roughly when , that is, for low-degree endpoints that lie far apart in the ordering. A full update can still cost as much as recomputation, and a break forces rebuilding the search trees; the gain is certifying a no-change update in for .
Verified executable and probe/pick count. A boolean-adjacency implementation refines the abstract update. An instrumented version counts legality checks and pick steps along the real control flow: exactly 1 for a no-break deletion, and at most for a no-break insertion.
The cost model. One cost unit is one legality check or one pick step. A unit is itself superconstant work: in the naive list-matrix implementation a pick filters the whole chosen list for each candidate, so one unit can cost up to . The model therefore compares our update with from-scratch recomputation within the same model. It says nothing about wall-clock parity with the linear-time static algorithm of Tarjan and Yannakakis [16]. What we count is a probe/pick count, not a verified resource bound in the sense of time credits [7], and § 7 says so again.
Preliminaries
Fix and write for the vertex set. A graph is a symmetric, loop-free binary relation equipped with proofs and . For a set and a vertex , write for the number of neighbours of inside . A vertex is a legal MCS pick for the chosen set if is maximum over ; it is a canonical pick if it is additionally smallest-index among the maxima. An ordering is an MCS ordering if every prefix picks legally.
Definition 1 (Canonical vs. set-valued). IsMCSOrdering is the canonical predicate: at each step the picked vertex is an MCS maximum with the smallest index. IsMCSOrderingAny drops the smallest-index clause and asserts only that each step is some MCS maximum. The canonical ordering of a graph is unique (IsMCSOrdering_unique); MCS(G) denotes the set of orderings satisfying IsMCSOrderingAny.
A single-edge update is modelled by FlipOf : agrees with except possibly on the pair , with , which covers inserting or deleting that edge. The update procedure insertUpdate is a general flip procedure: it keeps the ordering up to the first break it finds between the endpoints (all of it if there is none) and re-greedily rebuilds the suffix from there on the updated graph, and it is correct for any flip, not only an insertion. The deletion procedure is a parallel probe-then-repair procedure that probes only the later endpoint’s position. The executable layer works over a concrete boolean adjacency matrix Adj n = List (List Bool) with a transport to UGraph.
A common MCS prefix of and is a duplicate-free partial ordering whose every step is a legal MCS step in both graphs. We write IsCommonPrefix G G' p for the predicate that is such a prefix. The stability theorem of § 3 requires its tracking hypothesis only on the chosen sets of common MCS prefixes, and only for the vertices not yet chosen, not on every subset.
The stability theorem and obstructions
The main structural question is: when do and admit a common MCS ordering? The positive answer is stated under arbitrary tie-breaking, so it is about the sets and .
Theorem 2 (Common ordering, exists_common_ordering_prefix). Let , be graphs on vertices such that for every proper common MCS prefix () of and with chosen set , and every vertex ,
Then .
The lower bound already forces the update to be one-directional. Every vertex is a legal first pick, so every singleton is a common prefix, and the lower bound at gives for all , that is, (for both graphs are edgeless). Theorem 2 is therefore an insertion theorem; the deletion statements follow by exchanging the roles of and , and the “one-directional” condition in the abstract is implied by the hypothesis rather than added to it. The hypothesis is also not a practical test: it ranges over all common prefixes, and enumerating those is the same search that decides the conclusion. Theorem 2 is a structural sufficient condition; its usable content is the matching and flip corollaries below and the online extension.
The proof is an induction that builds the common ordering one vertex at a time. Its key step (exists_common_pick) is that every chosen set satisfying the bounds admits a vertex that is an MCS maximum in both graphs: let be the maximum count in over ; if some -maximizer gains 1 in it is maximal in both, and otherwise and every -maximizer works. The step compares unchosen vertices only, which is why the bounds are needed only for , and the induction visits only common prefixes.
Both restrictions matter. Requiring the bounds for every subset and every (exists_common_ordering, kept in the artifact) is equivalent to being plus a matching: forces , and forces . Theorem 2 is strictly more general. Inserting a into the edgeless graph on three vertices satisfies it: once one leaf is chosen, the centre is the only common next pick, so no common prefix contains both leaves without the centre. An exhaustive count over all insertion-only pairs with not a matching shows the effect of each restriction: on vertices, 48 pairs satisfy the bounds for every along common prefixes and 100 satisfy them for unchosen ; on the counts are 1,020 and 5,315. In the same count no pair satisfying the bounds lacks a common ordering, as the theorem requires.
Corollary 3 (Online form, common_order_extends_prefix). The induction in Theorem 2 is stronger than the theorem: under the same hypothesis, with the bounds required only along proper common MCS prefixes and only for unchosen vertices, any common MCS prefix extends to a full common MCS ordering of both graphs. A maintainer that, at each step, picks any vertex that is maximum in both graphs can therefore extend its prefix forever, with no lookahead and no backtracking. This is a separate entry in the verified artifact, proved by strong induction on the number of unplaced vertices. It also places the canonical update of § 4 in this picture: the prefix that update keeps is a common MCS prefix, which under the hypothesis extends to a common ordering; the update itself continues canonically in only.
We apply Theorem 2 to the update model. A matching is a graph in which every vertex has degree at most one.
Corollary 4 (Matching insertions/deletions, insert_matching_common_order, delete_matching_common_order). If is obtained from by inserting a matching, or by deleting a matching, then .
Corollary 5 (Single-edge flip, flip_common_order). A single-edge flip always preserves a common MCS ordering: for any with obtained from by flipping the edge , .
The hypotheses of Theorem 2 are precisely what one would try to relax, and both fail. The “+1” bound cannot become “+2”, and the assumption that the update is one-directional (all inserts or all deletes) cannot be dropped in general. Each negative result below is a concrete small instance, certified in the artifact by a pruned search whose soundness is itself a theorem and discharged by kernel decision on an explicit edge list (§ 8).
Theorem 6 (Certified obstructions: triangle_no_common_order, p4_no_common_order, two_p3_no_common_order, mixed_matching_no_common_order). The following four edge-modification sets each destroy every common MCS ordering:
Triangle (). Inserting a triangle into (adding $(2,3), (2,4), (3,4)) leaves no common MCS ordering: . The triangle has maximum -degree 2.
Path (). Inserting the triangle-free path 2–5–4–3 into the graph leaves no common ordering. Unlike the triangle, the inserted is triangle-free, so the obstruction does not reduce to the presence of a clique; both cases have maximum -degree 2.
Two paths (). Inserting (a ) into leaves no common ordering. With the triangle and it completes the three one-sided patterns used in the Star–Matching discussion of § 10.
Disjoint mixed pair (). Flipping the matching as one insertion and one deletion (deleting 01, inserting 23) into leaves no common ordering. The two flipped edges are disjoint, so the one-directional condition cannot be dropped for disjoint mixed pairs.*
Theorem 6 proves each obstruction on the stated witness only. Exhaustive computer search over all hosts (the Python enumerator and the C checker of § 8) finds no smaller witness: the smallest failing hosts have for the triangle, for , for and for the disjoint mixed pair. In particular, inserting a never destroys commonness on vertices, while 13,644 of the hosts on fail. When the two flipped edges of a mixed pair share a vertex, the same search found no failing host for . These minimality and no-failure facts are search results, not Lean theorems. No star-plus-matching pattern we tested ever failed: , and over all hosts up to , and , and up to .
The positive theorem is sufficient, not necessary. On four vertices, take and insert the two-edge path (a ). The common prefix leaves the centre 0 unchosen with its count raised by two, so the hypothesis fails, yet and still share an MCS ordering, for instance . A violation of the “+1” clause therefore does not by itself destroy commonness. The exact boundary is posed as an open problem in § 10.
Locality of a single-edge update
The canonical update is the probe-then-repair procedure: scan the current ordering for the first step whose old choice stops being the canonical MCS pick in the updated graph, and re-greedily rebuild only the suffix from that point. Its correctness is the local counterpart of the stability theorem.
Theorem 7 (Update correctness, init_valid, insert_update_valid, delete_update_valid, greedySuffix_full, update_from_prefix). Starting from a valid canonical ordering, a single insertion or deletion returns a valid canonical MCS ordering of the updated graph (insert_update_valid, delete_update_valid); the empty-prefix regreedy initializes correctly (init_valid), regreedying a full prefix is the identity (greedySuffix_full), and regreedying a prefix of a valid canonical ordering of the old graph whose steps are canonical in the updated graph yields a valid canonical ordering of the updated graph (update_from_prefix).
Theorem 8 (Update equals recompute, insert_update_eq_initOrder, delete_update_eq_initOrder, IsMCSOrdering_unique). The returned ordering is exactly the from-scratch canonical ordering of the updated graph; hence, by uniqueness of the canonical ordering, the maintained state is the canonical ordering, not just some valid one.
The locality of the probe is where the algorithm gains over recomputation.
Theorem 9 (Insertion window, legal_upto_earlierPos, legal_after_laterPos, insert_break_iff). For an insertion of with earlier than in the canonical order, every position up to ’s position and every position after ’s position keeps its old choice canonical in with respect to the old prefix; inside the open window , a step breaks exactly when the later endpoint now beats the old choice at that step.
Proof. The update adds the single edge . For a prefix at or before , contains neither endpoint, so every candidate count is unchanged and the old pick stays canonical. For after , both endpoints lie in , so they are not candidates and the counts of the remaining candidates from are identical in and ; the old pick stays canonical. For strictly inside the window, and , so is the only candidate whose count changes, rising by 1 (the new edge to ), and it breaks the step exactly when it overtakes the old pick. □
Theorem 10 (Deletion single-point, legal_upto_earlierPos, delete_legal_between, legal_after_laterPos). For a deletion of , only the later endpoint’s own position can be the first break; positions strictly between the endpoints keep their old choice canonical in .
Proof. The update removes . For a prefix at or before , neither endpoint is in , so no count from changes and the old pick stays canonical. For after , both endpoints are in and are not candidates, so the remaining counts are unchanged (legal_after_laterPos). For strictly between the endpoints, but : the count of drops by 1 (it loses neighbour ), while every other candidate’s count is unchanged. Since is not yet the pick, the old pick has before the drop and hence after it, so remains the maximum and canonical. Thus the first break can only occur at , where is itself the pick and its count drops.
Lemma 11 (No break at the later endpoint, no_break_at_laterPos). An insertion never breaks at the later endpoint’s own position; the window is the open interval , not the half-open .
Proof. At step the old pick is itself. Its count rises by 1 (because is already chosen), and every other unchosen count is unchanged. So becomes the strict maximum and stays canonical.
Lemma 12 (Old-graph break criterion, insert_break_iff_old). Inside the open window, with the old pick at step and the old maximum count, the step breaks exactly when
where is the count in the old graph.
Proof. At a step in the open window, only ’s count changes, from to , and . The step breaks exactly when ’s new count exceeds (i.e. ), or equals with a smaller index than the old pick (i.e. and ).
Both lemmas are comparator theorems of the artifact. The first justifies shrinking the probe window by one position; the executable does not exploit this and still checks (§ 7). The second makes the probe a question about old-graph data only, which § 5 exploits.
The update equals recompute, so the statement that the update is the identity exactly when the ordering is already canonical is a tautology given the update-equals-recompute theorem; the artifact retains it as an entry (§ 8) but we do not headline it.
A sublinear first-break probe
The insertion probe asks: is there a step in the open window at which the old pick stops being canonical in the updated graph? By Lemma 12 this is a question about the old-graph data . We prove the probe is answerable in time, independent of the window length.
Theorem 13 (Sublinear first-break probe). Store the canonical order together with the per-step data and, for each value , a balanced search tree over , keyed by position and augmented with the maximum of in each subtree. For an insertion of , the first position of the open window at which the old ordering breaks, or the fact that there is none, is computed in time, independent of the window length. After a no-break insertion, is unchanged and changes only at , by , so the structure is updated in time. Building it takes time and space once the canonical ordering and its per-step data are known; computing those takes time with a heap per count value for the smallest-index tie-break, against for the arbitrary tie-break of [16].
Proof. Two facts are machine-checked in the artifact. First, the count is a step function: adding one vertex changes it by 0 or 1, exactly per adjacency (neigh_take_succ), and its exact net change over an interval equals the number of neighbours of in that interval (neigh_take_sub_eq_count). Consequently takes at most distinct values across the window (neigh_take_image_card_le). This plateau bound is the machine-checked part; the tree queries, the descent and the plateau scan below are on paper. The plateau boundaries are the window positions just after a neighbour of , so sorting the positions of ’s neighbours yields them, and the initial value at the window start, in time. On each constant piece with , the criterion of Lemma 12 asks for the first with , or with and . The first is the successor of in the tree of ; the second is found by descending the tree of inside , skipping every subtree whose maximum is at most . Both cost . The pieces are scanned in window order and the scan stops at the first piece that yields a position; the earlier of its at most two candidates is the first break. With at most pieces the total is . After a no-break insertion only changes, so moves from the tree of to that of in . The win regime: the probe beats the naive scan roughly when , that is, for low-degree endpoints that lie far apart in the ordering. A full update after a break can still cost as much as recomputation, plus rebuilding the trees; the gain is certifying a no-change update in for . □
The break predicate is not monotone in . For example, on with and canonical order , insert : the open window is and the step function is (yes, no), so a break is followed by a non-break (no graph on three vertices shows this). This rules out a naive binary search on a single key, but the multi-plateau structure above is the right shape for the range queries. The sublinear bound is proved here on paper (the plateaus are machine-checked); it is not itself a Lean theorem, since the artifact has no formal cost model. As a sanity check, the artifact script scripts/probe_check.py compares the probe with from-scratch recomputation on 35,856 random insertions (): the reported first break equals the first changed position in every case, and on all 13,077 no-break insertions () is unchanged and changes exactly at , by +1.
Deletions. By Theorem 10 a deletion can first break only at , so locating the break is free. Deciding whether it fires is not determined by the stored data : on three vertices, the hosts and have the same canonical order and the same , yet deleting 01 changes the ordering of the first and not of the second. With per-step runner-up data, the largest count among unchosen vertices other than and the smallest vertex attaining it, the step at breaks iff , or and , an test (confirmed against recomputation on 35,925 random deletions). Keeping current is the obstacle: a no-break deletion can change runner-up data at other steps, and did so in 3,477 of 7,156 random no-break deletions. A sublinear maintained deletion probe is therefore open (§ 10).
Verified executable
To rule out the gap where a “specification” is proved but nothing executable implements it, the development carries a concrete boolean-adjacency implementation and proves it refines the abstract update.
Theorem 14 (Executable refinement, exec_insert_update_eq, exec_delete_update_eq, setEdge_preserves_symm, setEdge_preserves_loopless, mcsOrder_eq_greedySuffix). Let be symmetric, loop-free boolean adjacency matrices with , whose graphs and are related by a flip of (FlipOf G G' u v), and let be the canonical MCS
ordering of the old graph . Then
and likewise equals when is an edge of and not of . Setting or clearing the edge of a well-shaped symmetric matrix preserves symmetry, and preserves loop-freeness when ; the executable from-scratch MCS of a matrix is the value list of a canonical MCS ordering of its graph.
The artifact additionally carries theorems that certify recomputation, not the dynamic update: they state that recomputing the MCS of the flipped matrix from scratch is valid. The dynamic update is certified by the refinement theorem above (Section 8).
Probe/pick count along the real control flow
An instrumented variant of the executable update counts, at each step, one unit for a legality check and one unit for a pick step, and returns the count together with the ordering. Its first projection is provably the plain update (Section 8), so the counts below attach to the update that is actually run.
Theorem 15 (Probe/pick counts, exec_delete_cost_of_no_break, exec_insert_cost_of_no_break, exec_insert_cost_of_break, exec_delete_cost_of_break, exec_insert_cost_le, exec_delete_cost_le). Let . In the unit-cost model, where one unit is one legality check or one pick step, the following hold.
No-break deletion: if a deletion’s probe finds no break, the count is exactly 1 unit.
No-break insertion: if an insertion’s probe finds no break, the count is at most the window size for the two endpoints.
Break cost: a break at position costs the probe plus at most regreedy steps.
Worst case: at most units for insertion (given an ordering of length ), and at most for deletion. Both are within one unit of from-scratch recomputation in this model, which costs pick steps.
The two most useful statements are the first two: a no-break deletion costs one check, a no-break insertion costs a probe of the window. These are the operational content of the locality results of Section 4. The insertion bound counts the open window plus the later endpoint’s own position, which the executable probe also checks; by Lemma 11 that check never fires, so the proved bound is one unit above the open-window optimum.
A cost unit is superconstant in the naive list-matrix implementation: an adjacency lookup indexes a list-of-lists at , a cardinality check costs , and a pick calls it for every remaining candidate, so one pick costs , up to when both lists have length . The count is therefore a probe/pick count, weaker than a verified resource analysis in the sense of time credits [7]; it compares the update against from-scratch recomputation within the same model and says nothing about wall-clock parity with the linear-time static algorithm.
The Lean formalization
The development is a Lean 4 / Mathlib project, organized as a Palomar registry challenge and registered as Palomar entry PALOMAR-2026-10-04-000009.3 Version 3 is registered from commit ab521f2: status registered, review outcome neutral with no review warnings, trust level high. Its one trust reason is “Challenge exceeds the preferred audit surface” (742 lines). The commit pinned below differs from ab521f2 only in the axiom audit (AxiomAudit.lean and its CI script) and the README, so version 3 carries exactly the statements of this paper, and its external kernel re-checks (nanoda, con-ron) cover them. The registry records the source under the repository’s former name, thonmay/thesis-lean, which redirects to the current one. Version 3 supersedes two earlier versions. Version 2, from the ancestor commit c4c2c0f, requires the count bounds of Theorem 2 and Corollary 3 for every vertex rather than only for unchosen ones. Version 1, from the ancestor commit a872fdd, has 37 of the 41 comparator theorems and states the online corollary under every-subset bounds. Registration is a preservation and indexing service, not a review endorsement.
A module Challenge poses the headline statements, with explicit sorry bodies and canonical definitions in Mathlib-only code; a module Solution proves them. Both are generated from a single source of truth, so every posed statement is textually identical to its proved counterpart. The challenge/solution comparator lists 41 theorem names. By the section in which each is first named: 1 in the introduction, 1 in § 2, 13 in § 4, 9 in § 3, 5 in § 6, 6 in § 7, and 6 only in the formalization section below. The table groups them by the section where they are stated; the two names that first appear early (common_order_extends_prefix and IsMCSOrdering_unique) are stated in § 3 and § 4. They fall into these categories:
| Category | count | Where stated |
| update correctness | 5 | 4 |
| uniqueness / update = recompute | 3 | 4 |
| locality (incl. the two sharpening lemmas) | 6 | 4 |
| executable bridge | 3 | 6 |
| executable refinement | 2 | 6 |
| probe/pick count | 6 | 7 |
| stability (matching, flip, prefix extension) | 5 | 3 |
| every-subset special case | 1 | 3 |
| certified obstructions (triangle, , , mixed) | 4 | 3 |
| recomputation certs., tautologies, projection links | 6 | 8 |
| total | 41 |
Table 1.
Beyond the 41 comparator names, the development carries auxiliary and proof-engineering entries that the mathematical sections reference but do not headline: the key-step lemma exists_common_pick; the pruned-search soundness lemmas no_common_order_of_search and commonSearch_of_common; and the step-function facts neigh_take_succ, neigh_take_sub_eq_count and neigh_take_image_card_le that underpin the sublinear probe of § 5.
The comparator’s last row collects entries that certify the recomputation layer rather than the dynamic update: the tautological identity entries insert_update_eq_self_iff and delete_update_eq_self_iff, the recomputation-certifying entries exec_insert_recompute_valid and exec_delete_recompute_valid, and the first-projection links exec_insert_update_c_fst and exec_delete_update_c_fst that tie the instrumented count to the plain update.
Every theorem audits to only the three standard Lean axioms (propext, Quot.sound, Classical.choice): there is no sorry outside Challenge, and no native_decide. An AxiomAudit module prints the axioms of each comparator theorem and of the six auxiliary lemmas above, enforced as a CI step; a definitions-sync check enforces byte-identity of the canonical definitions; and an external kernel checker (leanchecker) re-validates each of the 20 source modules. The certified obstructions are independently cross-checked by the registry kernel re-checks (nanoda and con-ron) and by a separate exhaustive Python enumerator that reproduces each witness edge list exactly.
Artifact and reproducibility. The Lean development, its comparator, the axiom audit and the empirical verification scripts are public at https://github.com/thonmay/mcs-lean under the Apache-2.0 license, pinned to the annotated tag mcs-arxiv-v10 (commit 0d0ddff), which is also published as a GitHub Release and archived by Software Heritage.4 It differs from ab521f2 only in the axiom audit (AxiomAudit.lean and scripts/check_axioms.sh), which also covers the six auxiliary lemmas cited above, and in the README; the posed and proved statements are byte-identical. Palomar version 3 is registered from ab521f2 (see above). The README on the master branch maps every theorem named in this paper to its Lean source file and lists the exact build and verification commands (lake build, the AxiomAudit step and per-module leanchecker). The build pins leanprover/lean4:v4.35.0-rc2 because the Mathlib revision tracking master requires it; no stable release is compatible with that revision yet. An independent C checker (scripts/stab.c), written for the internal pre-submission review (see the AI disclosure), is included. It agrees with the Python enumerator on all four certified obstructions, a further cross-check of the witness edge lists.
The formalization is logically required for § 3–§ 7: every numbered theorem, corollary and lemma there except Theorem 13, and every certified obstruction, is a theorem in the repository. Five Python scripts are supporting, not proof premises. The exhaustive stability enumerator (scripts/mcs_stability.py) reproduces the counterexample witness edge lists. scripts/incomparability_witness.py enumerates the MCS and LexBFS ordering families over all tie-breaks on the witness of § 9 and certifies the 204/204/40 count. Finally, scripts/mcs_highn_crosscheck.py runs the adopted candidate implementation (scripts/candidates/gen003_c02.py) on random graphs up to , checking after every edge flip that its ordering is a legal MCS ordering and equals a from-scratch recomputation. scripts/prefix_hypothesis_count.py produces the exhaustive counts after Theorem 2, and scripts/probe_check.py the random-graph checks of § 5.
Related work
The nearest dynamic prior art maintains a property of a chordal graph through an object related to MCS, not the MCS ordering of an arbitrary graph. Ibarra [8] maintains a clique-tree representation of a chordal graph under insertions and deletions. Banerjee, Raman and Satti [1] maintain a perfect elimination ordering under deletions only, with a different window notion and a cell-probe lower bound for dynamic chordality. Mezzini [11] gives -query/-update chordal maintenance. None of these maintains the MCS ordering itself, and none is machine-checked.
Outside MCS, Morse and Kozsik [12] maintain a BFS ordering under edge updates: a framework for fully dynamic BFS spanning trees and their induced ordering in directed graphs, under both insertions and deletions. They discuss LexBFS only as a possible refinement and leave a dynamic LexBFS open. It is the closest sibling to our work, a maintained graph-search ordering of the same kind, but for BFS rather than MCS, and not machine-checked. Our result is specific to MCS orderings of undirected graphs, and it is the only one of these that is machine-checked.
The broader dynamic graph-search literature includes decremental BFS (the Even–Shiloach tree [15]), dynamic DFS (Baswana et al. [2]) and dynamic topological ordering (Pearce–Kelly [13]; Bender et al. [3]). Among verified dynamic graph algorithms, the closest is Guéneau et al. [7]: incremental cycle detection in Coq with time credits. Verified SCC algorithms have been formalized in Isabelle/HOL [9], and Lammich and Neumann [10] give an Isabelle framework for verified DFS. We found no prior formalization of MCS or of a perfect elimination ordering, and no machine-checked fully dynamic search-ordering maintenance, in the proof assistants we surveyed (AFP, Mathlib, Coq libraries, Why3). This is a negative claim, limited by that survey. MCS-M [4], a multi-sweep extension of MCS for computing minimal triangulations, is static and maintains no ordering under updates.
The incomparability of MCS and LexBFS orderings is due to Corneil–Krueger [6]. On a witness of this incomparability, a chordal 7-vertex graph, brute-force enumeration over all tie-breaks gives 204 MCS orderings and 204 LexBFS orderings, and each family has 40 orderings not in the other: . The witness is on , plus vertex 5 joined to 0 and vertex 6 joined to . Brandstädt, Dragan and Nicolai [5] show a common-perfect-elimination-ordering result for LexBFS powers that fails for MCS. It is adjacent prior art, negative where our stability statement is positive.
Conclusion and open problems
We have shown how the canonical MCS ordering behaves under single-edge updates: exact locality, a sublinear first-break probe, an executable refinement, a probe/pick count, and a stability theorem with certified obstructions for the set-valued MCS orderings. Everything except the probe bound is machine-checked. Three directions stand out.
The stability boundary. Conjecture (Star–Matching): for a one-sided update , for every host graph iff is a star plus a matching, i.e. at most one vertex has -degree . The matching side is proved here (Corollary 4); standard combinatorial reasoning shows a one-sided update with two vertices of -degree always contains a triangle, a or a as a subgraph, of which all three are certified here (Theorem 6). However, subgraph containment does not by itself give an obstruction for : commonness is not monotone in , because adding update edges can restore a common ordering. The “only if” direction therefore needs a lifting lemma (if has a bad host on vertices, then has a bad host on some ), which is not proved and is open. The star case needs a non-local inflation argument and is also open.
The adjacent mixed pair. The disjoint mixed pair is a certified obstruction. The adjacent mixed pair, where the two flipped edges share a vertex, never failed in our experiments (). A lemma proving that it always preserves a common ordering is the natural next addition.
A maintained deletion probe. A deletion can first break only at , and with per-step runner-up data the break test there is (§ 5). The data alone does not decide it, and a no-break deletion can change at other steps, so keeping the runner-up data current in sublinear time is open.
Acknowledgements and AI disclosure
This work was developed with AI assistance in accordance with the ELTE IK policy on the use of AI tools. Three models, each driven through an agent harness over Lean 4, participated. DeepSeek-V4-Flash-0731 (provider DeepSeek; model identifier deepseek-ai/DeepSeek-V4-Flash-0731; agentic tool mode, thinking mode on at default effort) carried the original development phase: the core definitions, the probe-then-repair updates, and their validity proofs, checked with lake build over Mathlib. Anthropic Claude Opus 5.5 (provider Anthropic; CLI coding-agent tool mode, high thinking mode) planned and drafted the resubmission, wrote the single-source canonical definitions, the locality and ExecUpdate modules, the stability module, and the unit-cost instrumentation, and ran the brute-force stability experiments and the revisions answering the internal reviews. Qwen3.8-27B-FP8 (provider Alibaba; model identifier Qwen/Qwen3.8-27B-FP8; agentic tool mode, thinking mode on at default effort) repaired the executable refinement and unit-cost proof bodies, contributed the certified stability counterexamples, and wired the comparator. In every phase the model’s proof state was machine-checked with lake build and independently re-checked by the leanchеcker external kernel; the transport and bridge lemmas were written by hand. A self-hosted text-rewriting model (Humanizer 12B, 8-bit quantized; plain text-completion mode, no reasoning mode) proposed rewordings of the prose sections and the repository README; every adopted change was applied by hand and checked against the Lean statements. The internal pre-submission review rounds, including the C checker scripts/stab.c and the witness, were produced by the second author with Anthropic Claude Opus 5.5 (CLI coding-agent tool mode, high thinking mode) in agent sessions; the probe and prefix-hypothesis check scripts were written by the first author with the same model, designed from those review findings. All findings were re-run and checked before being adopted. The human authors reviewed the resulting definitions, statements, proofs, experiments, and manuscript text and assume full responsibility for the final work. No AI system is an author.
Core Lean definitions
The following core definitions, and the Lean statement of Theorem 2, are reproduced verbatim (docstrings and proofs omitted) from the Challenge module of the artifact (tag mcs-arxiv-v10) so that readers can audit statement fidelity. The remaining definitions, among them AddsEdges, IsMatching, deleteUpdate and the helpers firstBreakWindow, earlierPos, laterPos and greedySuffix used in insertUpdate, are in the same module (Challenge.lean).
abbrev Vert (n : ℕ) := Fin n
structure UGraph (n : ℕ) where
adj : Vert n → Vert n → Prop
symm : ∀ {x y : Vert n}, adj x y → adj y x
loopless : ∀ (x : Vert n), ¬ adj x x
def neigh (G : UGraph n) (chosen : Finset (Vert n)) (w : Vert n) : ℕ := by
classical
exact chosen.card - (chosen.filter (fun x => ¬ G.adj w x)).card
def IsMCSNext (G : UGraph n) (chosen : Finset (Vert n)) (w : Vert n) : Prop :=
w ∈ (Finset.univ : Finset (Vert n)) \ chosen ∧
(∀ x : Vert n, x ∈ (Finset.univ : Finset (Vert n)) \ chosen →
G.neigh chosen x ≤ G.neigh chosen w) ∧
(∀ x : Vert n, x ∈ (Finset.univ : Finset (Vert n)) \ chosen →
G.neigh chosen x = G.neigh chosen w → w ≤ x)
def IsMCSOrdering (G : UGraph n) (order : List (Vert n)) : Prop :=
order.Nodup ∧ order.length = n ∧
∀ (i : ℕ) (hi : i < order.length),
IsMCSNext G (order.take i).toFinset (order.get ⟨i, hi⟩)
def IsMCSNextAny (G : UGraph n) (chosen : Finset (Vert n)) (w : Vert n) : Prop :=
w ∈ (Finset.univ : Finset (Vert n)) \ chosen ∧
∀ x : Vert n, x ∈ (Finset.univ : Finset (Vert n)) \ chosen →
G.neigh chosen x ≤ G.neigh chosen w
def IsMCSOrderingAny (G : UGraph n) (order : List (Vert n)) : Prop :=
order.Nodup ∧ order.length = n ∧
∀ (i : N) (hi : i < order.length),
IsMCSNextAny G (order.take i).toFinset (order.get ⟨i, hi⟩)
def IsCommonPrefix (G G’ : UGraph n) (P : List (Vert n)) : Prop :=
P.Nodup ∧ ∀ i (hi : i < P.length),
IsMCSNextAny G (P.take i).toFinset (P.get ⟨i, hi⟩) ∧
IsMCSNextAny G’ (P.take i).toFinset (P.get ⟨i, hi⟩)
def FlipOf (G G’ : UGraph n) (u v : Vert n) : Prop :=
u ≠ v ∧
∀ (x y : Vert n),
G’.adj x y = G.adj x y ∨ (x = u ∧ y = v) ∨ (x = v ∧ y = u)
def insertUpdate (H : UGraph n) (order : List (Vert n)) (u v : Vert n) : List (Vert n) :=
let k := Option.getD (firstBreakWindow H order (earlierPos order u v + 1)
(laterPos order u v)) order.length
greedySuffix H (order.take k)
theorem exists_common_ordering_prefix : ∀ {n : N} (G G’ : UGraph n),
(∀ (P : List (Vert n)),
IsCommonPrefix G G’ P → P.length < n →
∀ (x : Vert n), x ∉ P → G.neigh P.toFinset x ≤ G’.neigh P.toFinset x) →
(∀ (P : List (Vert n)),
IsCommonPrefix G G’ P → P.length < n →
∀ (x : Vert n), x ∉ P → G’.neigh P.toFinset x ≤ G.neigh P.toFinset x + 1)
→
∃ ord, G.IsMCSOrderingAny ord ∧ G’.IsMCSOrderingAny ord
The executable layer works over a concrete boolean adjacency matrix Adj = List (List Bool) with a transport toUGraph; the instrumented variant execInsertUpdateC returns the ordering together with the probe/pick count.
References
References
- [1]Niranka Banerjee, Venkatesh Raman, and Srinivasa Rao Satti. Maintaining chordal graphs dynamically: Improved upper and lower bounds. In Computer Science – Theory and Applications (CSR 2018), Lecture Notes in Computer Science, pages 29–40, 2018. doi: 10.1007/978-3-319-90530-3_4.DOI
- [2]Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic DFS in undirected graphs: Breaking the O(m) barrier. SIAM Journal on Computing, 48(4):1335–1363, 2019. doi: 10.1137/17M114306X.DOI
- [3]Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. A new approach to incremental cycle detection and related problems. ACM Transactions on Algorithms, 12(2):1–22, 2016. doi: 10.1145/2756553.DOI
- [4]Anne Berry, Jean R. S. Blair, Pinar Heggernes, and Barry W. Peyton. Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica, 39(4):287–298, 2004. doi: 10.1007/s00453-004-1084-3.DOI
- [5]Andreas Brandstädt, Feodor F. Dragan, and Falk Nicolai. LexBFS-orderings and powers of chordal graphs. Discrete Mathematics, 171(1–3):27–42, 1997. doi: 10.1016/S0012-365X(96)00070-2.DOI
- [6]Derek G. Corneil and Richard M. Krueger. A unified view of graph searching. SIAM Journal on Discrete Mathematics, 22(4):1259–1276, 2008. doi: 10.1137/050623498.DOI
- [7]Armaël Guéneau, Jacques-Henri Jourdan, Arthur Charguéraud, and François Pottier. Formal proof and analysis of an incremental cycle detection algorithm. In 10th International Conference on Interactive Theorem Proving (ITP 2019), volume 141 of LIPIcs, pages 18:1–18:20, 2019. doi: 10.4230/LIPIcs.ITP.2019.18.DOI
- [8]Louis Ibarra. Fully dynamic algorithms for chordal graphs and split graphs. ACM Transactions on Algorithms, 4(4):40:1–40:20, 2008. doi: 10.1145/1383369.1383371.DOI
- [9]Peter Lammich. Verified efficient implementation of Gabow’s strongly connected component algorithm. In 5th International Conference on Interactive Theorem Proving (ITP 2014), volume 8558 of Lecture Notes in Computer Science, pages 325–340, 2014. doi: 10.1007/978-3-319-08970-6_21.DOI
- [10]Peter Lammich and René Neumann. A framework for verifying depth-first search algorithms. In Proceedings of the 2015 Conference on Certified Programs and Proofs (CPP 2015), pages 137–146, 2015. doi: 10.1145/2676724.2693165.DOI
- [11]Mauro Mezzini. Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n²) update-time. Theoretical Computer Science, 445:82–92, 2012. doi: 10.1016/j.tcs.2012.05.002.DOI
- [12]Gregory Morse and Tamás Kozsik. Fully dynamic breadth first search and spanning trees in directed graphs, 2026. URL https://arxiv.org/abs/2604.12370.
- [13]David J. Pearce and Paul H. J. Kelly. A dynamic topological sort algorithm for directed acyclic graphs. ACM Journal of Experimental Algorithmics, 11, 2007. doi: 10.1145/1187436.1210590.DOI
- [14]Donald J. Rose, R. Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266–283, 1976. doi: 10.1137/0205021.DOI
- [15]Yossi Shiloach and Shimon Even. An on-line edge-deletion problem. Journal of the ACM, 28(1):1–4, 1981. doi: 10.1145/322234.322235.DOI
- [16]Robert E. Tarjan and Mihalis Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566–579, 1984. doi: 10.1137/0213035.DOI