Disjoint directed trails are preserved by restriction to a strongly connected component
ProvedDirKECC1549.Main.scc_disjoint_pathsdirected-graphsedge-connectivity
Let be a finite directed multigraph and let be the strongly connected component of a vertex . If and , then
This directional preservation result supports reductions of edge-connectivity questions to strongly connected components. Parallel edges retain their identities and loops are allowed.
Formalization Note The induced graph renumbers vertices and edges; the relation on its vertices is transported back to .
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem scc_disjoint_paths {n m : ℕ} (G : Fin m → Fin n × Fin n)
(a x y : Fin n) (k : ℕ) (hx : StronglyConn G a x) (hy : StronglyConn G a y) :
HasDisjointPaths G k x y ↔
liftRel (sccOf G a) (HasDisjointPaths (induced G (sccOf G a)) k) x y := by sorry
end DirKECC1549.MainSource
Auxiliary directional trail-transport lemma for Claim 1, Section 3.3, p.17, Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026). The statement is a generalization of the path-preservation step implicit in that claim.