Proof of paths sharing a common node?

Revision en4, by mohamedeltair, 2019-09-09 01:56:55

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.

#### History

Revisions

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