Let $G=(\mathcal{V}_G,\mathcal{A}_G)$ be an oriented acyclic graph. Assume that $G$ has a unique source $s\in \mathcal{V}_G$ and a unique sink $t\in \mathcal{V}_G$. Now, fix $u,v\in \mathcal{V}_G$ such that $(v,u)\in \mathcal{A}_G$. Is it true that there exists an oriented path in $G$ of type: $v_0=s, v_1, \cdots, v_i=v, v_{i+1}=u, \cdots, v_n=t$? In other words, is there an oriented path containing the arrow $(v,u)$, starting in the source and ending in the sink?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ What if $\mathcal V_G=\{s,t,u,v,w\}$ and $\mathcal A_G=\{st,vu,uw,wv\}$? Why isn't that a counterexample? Are you assuming some kind of connectedness for your graph? Does your definition of "path" allow repeated vertices? $\endgroup$– bofCommented Aug 20, 2020 at 1:42
-
3$\begingroup$ you could event add the edge $(sv)$ making your graph weakly connected without containing the desired path. On a side note, I don't see what does the condition $(st)\in\mathcal{A}_G$ do. A path from $s$ to $t$ through another vertex $u$ will never use this edge. $\endgroup$– Thomas LesgourguesCommented Aug 20, 2020 at 3:20
-
$\begingroup$ I forgot to mention, but the graphs I'm dealing with are acyclic. I think that the acyclic condition together with the uniqueness of the source/sink implies that $G$ is connected. Therefore, on the paths here, the vertices are not repeated, because this would generate a cycle. $\endgroup$– cl4y70n____Commented Aug 20, 2020 at 12:05
-
$\begingroup$ I don't know if condition $(s, t)\in\mathcal{A}_G$ is necessary (I don't think so). But, in the problem I'm working on, it is satisfied. $\endgroup$– cl4y70n____Commented Aug 20, 2020 at 12:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
With the acyclic condition, the answer is yes. Starting at $v$ and repeatedly following any edge exiting the current vertex, you will eventually end up at $t$, by acyclicity and uniqueness of the sink. Thus there exists a path from $v$ to $t$ and, similarly, there exists a path from $s$ to $u$, which shows what you want.
answered Aug 20, 2020 at 14:49