Disjoint trails in a walk-convex induced subgraph
ProvedDirKECC1549.Main.induced_disjoint_pathsdirected-graphsedge-connectivity
Let be a finite directed multigraph, let be a vertex set containing and , and assume that every edge of every directed walk from to has both endpoints in . For each ,
This transfers directional edge-connectivity to an induced subgraph. Parallel edges have distinct identities, and loops are permitted. The formal induced graph renumbers its vertices and edges.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem induced_disjoint_paths {n m : ℕ} (G : Fin m → Fin n × Fin n)
(S : Finset (Fin n)) (x y : Fin n) (k : ℕ) (hx : x ∈ S) (hy : y ∈ S)
(hwalk : ∀ p, IsWalk G x p y → ∀ e ∈ p, (G e).1 ∈ S ∧ (G e).2 ∈ S) :
HasDisjointPaths G k x y ↔
liftRel S (HasDisjointPaths (induced G S) k) x y := 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.