Lifting a walk to an induced subgraph
ProvedDirKECC1549.Main.induced_walk_liftdirected-graphsedge-connectivity
Let be a finite directed multigraph and let belong to a vertex set . Every directed walk from to whose edges have both endpoints in corresponds to a walk in the induced graph , with the same original edge identities after undoing the edge renumbering. This lifts individual walks to an induced subgraph, including parallel edges and loops.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem induced_walk_lift {n m : ℕ} (G : Fin m → Fin n × Fin n)
(S : Finset (Fin n)) (x y : Fin n) (hx : x ∈ S) (hy : y ∈ S)
(p : List (Fin m)) (hp : IsWalk G x p y)
(he : ∀ e ∈ p, (G e).1 ∈ S ∧ (G e).2 ∈ S) :
∃ q : List (Fin (inducedEdges G S).card),
q.map (fun i ↦ ((inducedEdges G S).orderIsoOfFin rfl i).1) = p ∧
IsWalk (induced G S) (posIn S x hx) q (posIn S y hy) := 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.