Claim 1 — k-edge-connectivity is decided inside strongly connected components
ProvedDirKECC1549.Main.claim_1directed-graphsedge-connectivityp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a directed multigraph, , and any vertices. Then if and only if and are strongly connected and , where is their strongly connected component and the induced subgraph.
This justifies the recursion of Algorithm 3, line 4, on the strongly connected components.
Formalization Note has its vertices renamed in increasing order; the second condition reads -edge-connectivity of the renamed copies of and in .
Differences from the source:
- generalization: directed graph with parallel edges (p.9) → self-loops also allowed; reason: a loop leaves no vertex set and can be deleted from any path, so it changes no out_D, no λ_D and no component; on loop-free multigraphs the statement is exactly the source's
- encoding: vertex set V and edge multiset E → vertices Fin n, edge ids Fin m, an edge map Fin m → Fin n × Fin n; reason: Lean convention; parallel edges are distinct ids, so every count includes multiplicities as on p.9; same instances
- encoding: edge-disjoint directed paths; λ_D(u,v) ≥ k → pairwise edge-disjoint trails (walks using no edge id twice); λ ≥ k as "k such trails exist"; reason: edge-disjoint walks shorten to edge-disjoint paths, so the counts agree
- reading: "for any u, v" with the k of Algorithm 3 → k ≥ 1; reason: the claim is used for k ≥ 1 (Algorithm 3's range); at k = 0 it is false: in the graph with two vertices and no edges, u ↔_0 v holds but u, v are not strongly connected
- encoding: the induced subgraph of their strongly connected component → G[S] with vertices renamed 0, …, |S|−1 in increasing order and its edges in increasing id order; reason: Lean convention for a subgraph as a graph on Fin |S|; same instances
Preamble
import Mathlib import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
/-- Claim 1, p.17: for `k ≥ 1` and any vertices `u, v`, `u, v` are `k`-edge-connected in `G`
iff they are strongly connected and `k`-edge-connected in the induced subgraph `G[S]` of their
strongly connected component `S`. -/
theorem claim_1 {n m : ℕ} (k : ℕ) (hk : 1 ≤ k) (G : Fin m → Fin n × Fin n) (u v : Fin n) :
KEdgeConnected k G u v ↔
StronglyConn G u v ∧
liftRel (sccOf G u) (KEdgeConnected k (induced G (sccOf G u))) u v := by sorry
end DirKECC1549.Main
Source
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 3.3, Claim 1 (in the proof of Lemma 4), p.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.