I am trying to show that the following property holds:
Definition A digraph is called a strongly connected graph if given two vertices $x \neq y$, there exist the oriented paths $x \rightarrow y$ and $y \rightarrow x$
Property A connected graph $G$ can be oriented to a strongly connected digraph if and only if every edge from $G$ belongs to a simple cycle in $G$.
I think I could prove the implication $\leftarrow$ :
Suppose $G$ can be oriented in such a digraph and takeand edge $e = (x,y)$ from $G$. In the oriented graph $G'$ obtained from $G$, there are two possibilities: $e$ was oriented as $x \rightarrow y$ or as $y \rightarrow x$.
Without loss of generality, suppose that $x \rightarrow y$ in $G'$. Since $G'$ is strongly connected, we have a simple oriented path $y \rightarrow x_1 \rightarrow … \rightarrow x_n \rightarrow x$.
We can then form the following simple cycle $C = (x,y,x_1,…,x_n,x)$ that satisfies $e \in C$.
Is the proof of $\leftarrow$ correct ? I got stuck trying to show $\rightarrow$. I thought of showing it by induction on the number of edges with base case number of edges $\geq 3$, but I could not prove the inductive step, I would appreciate any help. Thanks in advance.
Best Answer
Proof: Let $x$ and $y$ be any two arbitrary vertices in $G$ and let $x=x_0,x_1,\ldots, x_l, x_{l+1}=y$ be a sequence of vertices such that either $(x_i,x_{i+1})$ is an arc in $G$ or $(x_{i+1},x_i)$ is an arc in $G$ (or both) for each $i=0,\ldots, l$. As $G$ is connected there indeed exists such a sequence.
Then as there exists a cycle $C_i$ containing both $x_i$ and $x_{i+1}$ (in particular either $(x_i,x_{i+1})$ or $(x_{i+1},x_i)$ whichever is in $G$), it follows that $x_i$ and $x_{i+1}$ are in the same strongly connected component of $G$, for each $i=0,\ldots, l$. Thus, $x=x_0$ is in the same strongly connected component of $G$ as $x_{l+1}=y$ is, for any such $x$ and $y$, and so by definition of strongly connected, $G$ is indeed strongly connected. And so the $\rightarrow$ direction follows too. $\surd$