3
$\begingroup$

I'm trying to prove the following.

There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge.

(An orientation of an undirected graph is a directed graph made by replacing each edge $uv$ with exactly one of the directed edges $(u,v)$ and $(v,u)$; a directed graph is strongly connected if it contains a directed path from $u$ to $v$ for every pair of distinct vertices $u$ and $v$; a bridge is an edge whose deletion disconnects the graph.)

I can prove just one side. Assume that there is no bridge in the graph. So, for vertices $u$ and $v$, we can remove the edge which is between them and still there are(is) some paths(path) in the graph which we can reach $v$ from $u$ (so still the graph is connected). Because there is no bridge in the graph and every pair of vertices are reachable from the other without the edge of between them, we can convert the undirected graph to directed graph.

how about the other side? how can I prove that?

Can I say that, because the graph is undirected and it can be converted to a digraph, for each arbitrary pair of vertices $u$ and $v$ there is a path (or maybe some paths) which we can reach $v$ from $u$ and vice versa except the directed path of between them (the edge between them). So we can remove the directed path of between them. So there is no bridge edge in the graph.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The other direction is actually the easy direction. If there’s a bridge $uv$ and you orient the edge $u\to v$ then there is no directed path from $v$ to $u$. The proof that you gave for the hard direction doesn’t make any sense, unfortunately. $\endgroup$
    – Yuval Filmus
    Dec 7, 2018 at 16:32

1 Answer 1

Reset to default
3
$\begingroup$

If $uv$ is a bridge then any orientation of $G$ either includes the edge $u\to v$ and has no path from $v$ to $u$, or vice-versa.

If $G$ has no bridge, then it is $2$-connected. A graph is $2$-connected if, and only if, it can be decomposed as $C\cup P_1 \cup\dots \cup P_k$ where $C$ is a cycle and each $P_i$ is a path (possibly just a single edge) that intersects $C\cup P_1\cup\dots\cup P_{i-1}$ at both its endpoints and nowhere else. Now construct your strongly connected orientation from this decomposition.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How do you prove the existence of this decomposition? $\endgroup$
    – DreamConspiracy
    Dec 7, 2018 at 17:58
  • 2
    $\begingroup$ @DreamConspiracy Any $2$-connected $G$ contains a cycle so it has a maximal subgraph $H$ that can be built in the way I described. If $H=G$, we're done. Otherwise, consider some vertex in $G\setminus H$. By $2$-connectivity, it sends two disjoint paths to $H$, so we could add those to $H$, contradicting its maximality. $\endgroup$
    – David Richerby
    Dec 7, 2018 at 18:06
  • $\begingroup$ @DavidRicherby what is nbsp:G? is it abbreviation of something? (sry I havn't seen it before) $\endgroup$
    – siaVash
    Dec 7, 2018 at 20:13
  • $\begingroup$ @Yahya Sorry, typo. I was trying to insert an HTML non-breaking space to avoid putting a line break between "of" and "G" but I typed &nbsp: instead of ` $ (colon instead of semi-colon). Thanks for pointing it out! $\endgroup$
    – David Richerby
    Dec 7, 2018 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.