Make an undirected graph a strongly connected component (SCC)

Question

Let G(V,E), an undirected, connected graph with no bridges at all. Describe an algorithm which direct the edges, so the new graph is an SCC.

My suggested algorithm
So we run DFS from an arbitrary vertex. We notice that since it's an undirected graph there are only tree-edges and back-edges (Right?). We connect edges accordingly (a tree-edge would be directed "down" and a back-edge would be directed "up").

A start of proof
We notice that the graph has no bridges. Therefore, every edge is part of some cycle. Therefore, the last edge to be discovered in some cycle must be a back-edge.

Now, I think the rest of the proof would need to show that we can always "climb" to the root, and so the graph is an SCC.

I'd be glad if you could help me connect the dots (or vertices XD)

Thanks

Answer 1

What you are looking for is a proof for Robbins' Theorem.
For a more formal proof you can look at this paper (See proof for theorem 2).

The below is not a formal proof but it's a way you can think of it:

As you already mentioned, since there are no bridges, every edge is a part of some cycle. Since you want your output graph to be SCC, a DFS on this output graph (from any vertex) must only have back-edges and tree-edges. It cannot have forward-edges or cross-edges.

Lets assume we have a forward-edge from s to t. This means that in the DFS we ran in order to build the graph, t was discovered in the sub-DFS (recursive call) of s and had no other gray or white adjacents. But this is not true because whenever we discover t in our DFS we would still have a gray adjacent.

Lets assume we have a cross-edge from s to t. This means that t's sub-DFS has ended before s was discovered. Again, this cannot happen in our DFS because either when discovering t first we would discover s in its sub-DFS or the opposite direction.

Here is a simple graph to help you see those cases.