### mohamedeltair's blog

By mohamedeltair, history, 5 years ago,

In a directed graph, a pair of nodes $(a,b)$ is good if we have at least:

1) One path $x$ starting at a node with indegree 0 and ending at $a$.

2) And one path $y$ starting at a node with indegree 0 and ending at $b$.

Where $x$ and $y$ don't share any node. It turns out that $(a,b)$ is not good only if:

1) At least $a$ or $b$ is/are not reachable from a node with indegree 0.

2) Or all paths which start at node with indegree 0 and end at $a$ or $b$ share at least one common node.

What is the proof of the $2^{nd}$ point?

Note: The graph can be cyclic, but no self loops or parallel edges.

• +18

 » 5 years ago, # |   +22 Hint: rewrite the problem as an instance of maxflow and consider the minimum cut.
•  » » 5 years ago, # ^ |   +1 So, if we guarantee that both node $a$ and $b$ are reachable for node/s with in-degree $0$, and:1) Added a source node $S$ with out-going edges to all nodes with in-degree $0$.2) Added a sink node $T$ with in-going edges from $a$ and $b$.3) Split every node $i$ (except $S$ and $T$) to $2$ nodes $i_1$ and $i_2$, with an edge from $i_1$ to $i_2$ (to guarantee that all used paths don't share any nodes).4) Set the capacities of all edges to $1$.Then ran max flow, it will be $1$ if $(a,b)$ is not good, which means min cut is $1$ too. So, the minimum number of edges which if are removed the graph will be disconnected is $1$. The min cut edge can be:1) From $S$ to node $i$ (which means any path will have $i$).2) Or from node $i_2$ to node $j_1$ (which means any path will have the edge $(i,j)$, which implies having nodes $i$ and $j$).3) Or from node $i_1$ to node $i_2$ (which means any path will have node $i$).Thanks a lot for the useful hint.