Observation 1 — (k, Δ)-connectivity is an equivalence relation
ProvedDirKECC1549.Main.observation_1directed-graphsedge-connectivityp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a directed multigraph and integers. Call -connected if no -out set (, ) with , for any , contains exactly one of . Then -connectivity is an equivalence relation on .
Lemma 1 refines each -edge-connected component into these classes.
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
- generalization: k ≥ 2 and Δ ≥ k − 1 (standing in §3.1) → all integers k, Δ ≥ 0; reason: the observation holds for every k, Δ and specializes to the source's range
Preamble
import Mathlib import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
/-- Observation 1, p.11: `(k, Δ)`-connectivity is an equivalence relation on `V(G)`. -/
theorem observation_1 {n m : ℕ} (k Δ : ℕ) (G : Fin m → Fin n × Fin n) :
Equivalence (KDeltaConnected k Δ G) := by sorry
end DirKECC1549.Main
Source
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 3.1, Definition 1 and Observation 1, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.