Directed walks between vertices in a strongly connected component remain in it
ProvedDirKECC1549.Main.walks_in_sccdirected-graphsedge-connectivity
Let be a finite directed multigraph, and let be the strongly connected component of . If , then for every directed walk from to and every edge on ,
This is the walk convexity of strongly connected components; loops and parallel edges are allowed.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem walks_in_scc {n m : ℕ} (G : Fin m → Fin n × Fin n) (a x y : Fin n)
(hx : StronglyConn G a x) (hy : StronglyConn G a y) :
∀ p, IsWalk G x p y → ∀ e ∈ p, (G e).1 ∈ sccOf G a ∧ (G e).2 ∈ sccOf G a := by sorry
end DirKECC1549.Main
Source
Auxiliary lemma for Claim 1, Georgiadis, Kipouridis, Kosinas, Papadopoulos, Pergaminelis, STOC 2027 submission #1549, Section 3.3, p.17; derived supporting graph-theoretic statement.