Section 2, p.9 — k-edge-connectivity is an equivalence relation
ProvedDirKECC1549.Main.sec2_kecc_equivalencedirected-graphsedge-connectivityp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a directed multigraph and an integer. The relation (, or at least pairwise edge-disjoint directed paths from to and at least from to ) is reflexive, symmetric and transitive. Its classes are the -edge-connected components, forming the partition .
This makes well defined, which every later statement uses.
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
- generalization: the fixed integer k ≥ 2 of p.9 → every k ≥ 0; reason: the relation is defined for every k and the statement specializes to k ≥ 2
Preamble
import Mathlib import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
/-- §2, p.9: the `k`-edge-connectivity relation of a directed multigraph is an equivalence
relation (its classes are the `k`-edge-connected components `P_k(D)`). -/
theorem sec2_kecc_equivalence {n m : ℕ} (k : ℕ) (D : Fin m → Fin n × Fin n) :
Equivalence (KEdgeConnected k D) := by sorry
end DirKECC1549.Main
Source
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 2, p.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.