§ Pavel: bridges, articulation points for UNDIRECTED graphs

• Two vertices are 2-edge connected if there are 2 paths between them. The two paths cannot share ANU edges.
• Every bridge must occur as a DFS tree edge, because DFS connects all components together.
• More generally, every spanning tree contains all bridge edges.
• Now we check if each edge is a bridge or not.
• To check, we see what happens when we remove the edge $(u, v)$. If the edge is not a bridge, then the subtree of $v$ must connect to the rest of the graph.
• Because we run DFS, the subtree rooted at $v$ must go upwards , it cannot go cross. On an undirected graph, DFS only gives us tree edges and back edges.
• This means that if the subtree rooted at $v$ is connected to the rest of the graph, it must have a backedge that is "above" $u$, and points to an ancestor of $u$.
• Instead of creating a set of back edges for each vertex $v$, we take the highest / topmost back edge, since it's a safe approximation to throw away the other back-edges if all we care about is to check whether there is a backedge that goes higher than $u$.
• To find the components, push every node into a list. When we find an edge that is a bridge, take the sublist from the vertex $v$ to the end of the list. This is going to be one connected component. We discover islands in "reverse order", where we find the farthest island from the root first and so on.

§ Vertex connectivity

• The problem is that vertex connectivity is not an equivalence relation on vertices!
• So we define it as an equivalence relation on edges .
• More subtle, we cannot "directly" condense. We need to build a bipartite graph, with components on one side and articultion points on the other side.