Projecting an induced-subgraph walk to the original graph
ProvedDirKECC1549.Main.induced_walk_projectdirected-graphsedge-connectivity
Let be a finite directed multigraph and let belong to a vertex set . Every directed walk from to in the induced graph maps to a directed walk from to in by replacing each induced edge identifier by its original edge identifier. This projects walks while retaining edge identities, including parallel edges and loops.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem induced_walk_project {n m : ℕ} (G : Fin m → Fin n × Fin n)
(S : Finset (Fin n)) (x y : Fin n) (hx : x ∈ S) (hy : y ∈ S)
(q : List (Fin (inducedEdges G S).card))
(hq : IsWalk (induced G S) (posIn S x hx) q (posIn S y hy)) :
IsWalk G x (q.map (fun i ↦ ((inducedEdges G S).orderIsoOfFin rfl i).1)) y := by sorry
end DirKECC1549.Main
Source
Derived auxiliary walk transport lemma for Claim 1, Georgiadis et al., STOC 2027 submission #1549, Section 3.3, p.17.