Proof of paths sharing a common node?

Revision en3, by mohamedeltair, 2019-09-09 00:44:10

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) 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English mohamedeltair 2019-09-09 01:56:55 6
en3 English mohamedeltair 2019-09-09 00:44:10 82
en2 English mohamedeltair 2019-09-09 00:41:58 2 Tiny change: ' is good id we have a' -> ' is good if we have a'
en1 English mohamedeltair 2019-09-09 00:40:15 564 Initial revision (published)