How can I prove that this graph can still be strongly connected?

Question

Assume G is a directed and strongly connected graph with $n$ vertices and $2n-1$ edges. Prove that there is an edge like $e$ that $G-e$ is still strongly connected.

Any hints to start the proof?

Answer 1

Lets launch ourself at a randomly chosen vertex $r$ of this graph. Lets call it root. From this root we can achieve each remaining vertex $v$ of $G$. It means that there exists a tree $T_{r\rightarrow*}$ rooted in $r$ such that it connects $r$ with each of the other vertices. The number of edges in $T_{r\rightarrow*}$ is exactly $n-1$.

$T_{r\rightarrow*}$ can be build as follows. Take all the paths from $r$ to the others. Iteratively do: if two paths somewhere meet each other $\Rightarrow$ delete the heading edge of one of them. This will result in receiving a tree.

The same way we can derive $T_{r\leftarrow*}$ with a property that each vertex $v\in G$ is connected with $r$ through the edges of $T_{r\leftarrow*}$. The constructon of $T_{r\leftarrow*}$ is essentially the same. And it has $n-1$ edges as well.

So, note that having only the edges of $T_{r\leftarrow*}\cup T_{r\rightarrow*}$ is sufficient to have strong connectivity. But they have only $2(n-1)$ edges in total.

So, the last remaining edge $(2n-1) - 2(n-1) = 1$ could be deleted.