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

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.

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$.
• If $x$ has a path to $z$ and $y$ has a path to $x$, what does that imply about $x$ and $z$? Actually I notice I was very unclear about what I meant by "other vertex", will edit to clarify. Commented Feb 22, 2018 at 21:52