Graph Theory37 sections · 1633 units
Open in Course

DFS Tree Example

(Tree edges vs back edges)

Graph: 121-2, 232-3, 313-1, 242-4. Start DFS at 11. Tree edges: 121-2, 232-3, 242-4. Back edge: 313-1 (connects 33 back to ancestor 11). Edge 242-4 is a bridge because there is no back edge providing an alternate path to 44.

Vertex 44 is a dead end. Edges 121-2 and 232-3 are not bridges because back edge 313-1 creates a cycle, providing an alternate path between any two vertices in the triangle.