Prove that if G is nearly strongly connected there exists vertex such that every vertex is reachable

864 Views Asked by At

Given a directed graph $G = (V, E)$, the strongly connected components graph $G^{SCC}$ of $G$ is the directed graph defined by $V^{SCC} = \{C \mid C\ \text{is a}\ SCC\ \text{of}\ G\}$ and $E^{SCC} = \{(C_i, C_j) \mid \exists(u, v) \in E\ \text{where}\ u \in C_i, v \in C_j\}$. $G$ is nearly strongly connected if for each pair of vertices $s, t \in V$, either there exists a path from $s$ to $t$ or a path from $t$ to $s$.

Prove that if directed graph $G = (V, E)$ is nearly strongly connected then there exists a vertex $x \in V$ such that every vertex in $V$ is reachable from $x$.

How would I go about proving this?

I have tried drawing a diagram and saw that

    (+)
  /    \ 
(+)    (+)
  \
    \ 
      \ 
       (+)

the nodes connect criss cross and double everytime you add any.

1

There are 1 best solutions below

3
On

Hint: choose $x$ to be a vertex which has paths to as many other vertices as possible, and show that if $x$ doesn't have a path to $y$ then $y$ can't have a path to $x$.