Intersecting paths in a directed graph

245 Views Asked by At

I am stuck with the proof. Computer simulation cannot find a counterexample.

Given a directed graph (digraph) $G = (V,E)$ and two vertices $s,t \in V$ called the source and sink, we assume that there is a simple (without self-intersections) directed path from $s$ to $t$. Moreover, every directed edge $e \in E$ belongs to such a path. Sink $t$ has no outgoing edges.

To each $e \in E$ we assign two strictly positive real numbers $c(1,e)$ and $c(2,e)$. We assume (for simplicity) that all directed paths from $s$ to $t$ have pairwise distinct sums of numbers $c(1,e)$ and of numbers $c(2,e)$ as well.

The vertex-set $V - t$ is partitioned into $V_1$ and $V_2$. Let us fix an outgoing edge for each $v \in V_1$ (respectively, for each $v \in V_2$) and delete all other edges from $v$. In the obtained reduced digraph $G'$, determine the directed path from $s$ to $t$ that has the minimum sum of $c(1,e)$ (respectively, of $c(2,e)$). If $G'$ has no directed path from $s$ to $t$ then just choose nothing.

Do so for all possible selections of edges from $V_1$ and $V_2$.

Prove (or disprove) that the obtained two sets of directed paths from $s$ to $t$ intersect (have at least one common edge).