Two-Edge Connected Graph

Tags

Two-Edge Connected Graph

Category

Graphs

Difficulty

Very Hard

Problem Statement

Given an undirected, connected graph represented as an adjacency list, determine whether the graph is two-edge-connected. A graph is two-edge-connected if it remains connected after the removal of any single edge. Equivalently, a graph is two-edge-connected if and only if it has no bridges (a bridge is an edge whose removal disconnects the graph).

Intuition

The problem reduces to finding whether any bridge exists in the graph. If no bridge exists, the graph is two-edge-connected. We use a DFS-based approach similar to Tarjan's bridge-finding algorithm. During DFS, each node gets a discovery time and we compute the lowest discovery time reachable through back edges (the low value). An edge (u, v) where v is a child of u in the DFS tree is a bridge if and only if low[v] > disc[u], meaning there is no back edge from the subtree rooted at v that reaches u or any of its ancestors.

Approach

  1. Initialize disc and low arrays of size n to -1 (unvisited). Maintain a global timer starting at 0.
  2. Run DFS from any node (e.g., node 0).
  3. In the DFS at node u with parent parent:
    • Set disc[u] = low[u] = timer++.
    • For each neighbor v of u:
      • If v is unvisited: recurse on v with parent u. After returning, set low[u] = min(low[u], low[v]). If low[v] > disc[u], edge (u, v) is a bridge; return false.
      • If v is visited and v != parent: set low[u] = min(low[u], disc[v]).
  4. If DFS completes without finding any bridge, return true.
  5. Also verify the graph is connected (all nodes visited). If not, return false.

Pseudocode

function isTwoEdgeConnected(graph):
    n = number of nodes in graph
    if n <= 1:
        return true

    disc = array of size n, initialized to -1
    low  = array of size n, initialized to -1
    timer = 0
    hasBridge = false

    function dfs(u, parent):
        disc[u] = low[u] = timer
        timer += 1
        for v in graph[u]:
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    hasBridge = true
                    return
            else if v != parent:
                low[u] = min(low[u], disc[v])

    dfs(0, -1)

    // Check connectivity
    for i from 0 to n-1:
        if disc[i] == -1:
            return false  // not connected

    return not hasBridge

Time & Space Complexity

  • Time: O(V + E) where V is the number of vertices and E is the number of edges. This is a single DFS traversal.
  • Space: O(V) for the disc and low arrays plus the recursion stack (which can be O(V) in the worst case for a linear graph).

Key Insights

  • Two-edge-connectivity is equivalent to the absence of bridges. This is the defining structural property.
  • The low value of a node represents the earliest discovered ancestor reachable via a back edge from the node's subtree.
  • The condition low[v] > disc[u] (strictly greater, not >=) is what distinguishes bridges from non-bridges. If low[v] == disc[u], there is a back edge to u itself, so removing (u, v) does not disconnect the graph.
  • Be careful with multigraphs: if there are parallel edges between u and v, the edge (u, v) is not a bridge. The parent check needs to handle this by tracking the specific edge index rather than just the parent node.
  • Two-edge-connectivity is different from two-vertex-connectivity (biconnectivity). A graph can be two-edge-connected but not biconnected.

Edge Cases

  • Single node, no edges: Trivially two-edge-connected (no edge to remove).
  • Two nodes, one edge: Removing that edge disconnects the graph; not two-edge-connected.
  • Simple cycle: Two-edge-connected (every edge is part of a cycle).
  • Tree (any tree with > 1 node): Every edge is a bridge, so never two-edge-connected.
  • Disconnected graph: Not even one-edge-connected, so certainly not two-edge-connected.
  • Self-loops: Typically ignored since removing a self-loop does not disconnect anything.
  • Parallel edges: Two parallel edges between the same pair of nodes mean neither is a bridge.

Linked mentions