# Why does DFS solve Robbin's Theorem?

I've read over the proof for Robbin's Theorem, but I am not seeing why DFS will always give you a correct orientation of directed edges to solve the problem.

• Idea: Think about the augmented DFS procedure for finding bridges. If an edge is a bridge $\leftrightarrow$ there are no back edges in the descendants of the current vertex in the DFS spanning tree. – BearAqua Mar 24 '19 at 21:45
• Is there any chance you could expand on that just a bit? I think I get the gist of what you are saying but still not sure. – halfquarter Mar 24 '19 at 21:58
• Your 2-edge-connected graph is always bridgeless, meaning there's always a back edge to root. What remains is making all the back edges point in the right direction such that there's always a way to visit a vertex's ancestors in the DFS spanning tree. Also - DFS doesn't solve Robbins' theorem; Robbins' theorem states that you can generate a strongly connected digraph from a undirected graph iff the undirected graph is connected and has no bridge. (en.wikipedia.org/wiki/Robbins%27_theorem) – BearAqua Mar 24 '19 at 22:10
• @bearaqua care to write an answer instead of just commenting? – John L. Mar 24 '19 at 23:59