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.

$\endgroup$
  • 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 '18 at 16:32
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.

$\endgroup$
  • $\begingroup$ How do you prove the existence of this decomposition? $\endgroup$ – DreamConspiracy Dec 7 '18 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 '18 at 18:06
  • $\begingroup$ @DavidRicherby what is nbsp:G? is it abbreviation of something? (sry I havn't seen it before) $\endgroup$ – Yahya Dec 7 '18 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 '18 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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