Cycle Detection in Undirected Graph, in depth: the E = V - C test, parent-edge DFS that returns the cycle, union-find for edge streams and the multigraph traps

What counts as a cycle

Start with the definition, because the corner cases all live there. In a simple graph (no self-loops, at most one edge between two vertices) a cycle needs at least three vertices: a, b, c, back to a. In a multigraph two parallel edges between u and v already form a cycle of length two, and a self-loop on u is a cycle of length one. Which definition applies is a property of your data, not of the algorithm. Edge lists exported from real systems routinely contain duplicates: two links between the same pair of switches, or the same friendship recorded twice. Decide up front whether a duplicate is a real second edge or noise to deduplicate.

A connected undirected graph with no cycle is a tree. A graph with no cycle at all is a forest, meaning every connected component is a tree. Cycle detection is therefore the same question as "is this graph a forest?", and that reframing gives the cheapest test of all.

The counting test: forests have E = V - C

A tree on k vertices has exactly k - 1 edges. Sum that over the C components of a forest and you get the identity E = V - C. Any extra edge inside a component joins two vertices that are already connected, so it closes a cycle. That gives a test with no search at all: a graph is a forest if and only if E = V - C. If you already know C, for example from a connected-components pass you were running anyway, cycle detection is one subtraction.

The surplus E - V + C has a name, the cyclomatic number, and a meaning: it is the dimension of the cycle space. Equivalently, it is the number of edges you must delete to leave a spanning forest, and the number of independent cycles from which every other cycle can be built by symmetric difference. In circuit analysis it is the number of independent loop equations Kirchhoff's voltage law gives you. For the example graph V = 8, E = 7 and C = 2, so the cyclomatic number is 7 - 8 + 2 = 1: exactly one independent cycle.

The limit: counting says a cycle exists, not where, and computing C costs a traversal anyway.

DFS that skips the parent edge

Depth-first search on an undirected graph produces only two kinds of edge: tree edges, which discover a new vertex, and back edges, which connect a vertex to one of its ancestors. There are no cross edges in the undirected case, because DFS would have explored such an edge from whichever endpoint it visited first. A back edge plus the tree path between its endpoints is a cycle, so a graph has a cycle exactly when DFS finds a back edge.

The trap is the edge you arrived by. From v, the tree edge back to parent u looks like an edge to an already-visited ancestor. The common fix is "skip the neighbour equal to the parent vertex", and it is wrong for multigraphs. With two parallel edges between 0 and 1, both lead from 1 to its parent 0, so both get skipped and the length-two cycle is missed. The correct fix is to skip the parent edge, identified by its index in the edge list. The second parallel edge has a different id, is treated as a back edge, and the cycle is found.

The code below does that, uses an explicit stack instead of recursion, and walks parent pointers to return the cycle rather than a boolean:

def find_cycle(n, edges):
    """Return the vertices of one cycle, or None. edges: list of (u, v).
    Parallel edges and self-loops are allowed and count as cycles."""
    adj = [[] for _ in range(n)]
    for eid, (u, v) in enumerate(edges):
        adj[u].append((v, eid))
        adj[v].append((u, eid))
    parent = [-1] * n          # parent vertex in the DFS tree
    parent_edge = [-1] * n     # id of the edge used to reach the vertex
    depth = [-1] * n
    for root in range(n):
        if depth[root] != -1:
            continue
        depth[root] = 0
        stack = [(root, 0)]    # (vertex, index of next neighbour to try)
        while stack:
            u, i = stack[-1]
            if i == len(adj[u]):
                stack.pop()
                continue
            stack[-1] = (u, i + 1)
            v, eid = adj[u][i]
            if v == u:
                return [u]                     # self-loop: cycle of length one
            if eid == parent_edge[u]:
                continue                       # the edge we arrived by
            if depth[v] == -1:
                parent[v], parent_edge[v], depth[v] = u, eid, depth[u] + 1
                stack.append((v, 0))
            elif depth[v] < depth[u]:          # back edge to an ancestor
                cycle = [u]
                while cycle[-1] != v:
                    cycle.append(parent[cycle[-1]])
                return cycle[::-1]
    return None

Each vertex is pushed once and each adjacency entry is examined once, so the cost is O(V + E) time and O(V + E) memory for the adjacency list. The outer loop over roots handles disconnected graphs. Forgetting it is the classic bug that reports "no cycle" for a graph whose cycle lives in a component that does not contain vertex 0.

Worked example

Run it on the graph in the diagram, with edges e0 = (0, 1), e1 = (1, 2), e2 = (2, 3), e3 = (3, 4), e4 = (1, 5), e5 = (4, 1) and e6 = (6, 7). DFS starts at 0 and reaches 1 through e0. The adjacency list of 1 is [(0, e0), (2, e1), (5, e4), (4, e5)]. Skipping the arrival edge e0, the search descends through 2 and 3 to 4 at depth 4. From 4, after skipping e3, edge e5 leads to vertex 1 at depth 1: a back edge. Walking parent pointers from 4 gives 4, 3, 2, 1, and reversing gives the reported cycle. Vertex 5 is never visited because the function returns first. The run printed:

cycle: [1, 2, 3, 4]
first closing edge: 5 (4, 1)
V E C 8 7 2 cyclomatic 1
parallel: [0, 1]
self loop: [0]
tree: None
big cycle len: 200000
recursion limit: 1000

The last two lines are the reason for the explicit stack. A ring of 200,000 vertices puts every vertex on the DFS path at once. A recursive version would need 200,000 nested calls, and CPython's default recursion limit is 1,000. Raising the limit is fragile and can crash the interpreter outright. The explicit stack keeps the path on the heap and found the full 200,000-vertex cycle.

Union-find for edges that arrive over time

Union-find sees the graph as a stream of edges instead of an adjacency structure. Keep one set per connected component. For each edge (u, v), if find(u) == find(v) before the union, then u and v were already connected and this edge closes a cycle. Otherwise merge the two sets. The internals (union by size, path compression, the inverse-Ackermann bound) are covered in Union-Find, in depth. Here is what the cycle test needs:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                 # already connected: cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True


def first_closing_edge(n, edges):
    dsu = DSU(n)
    for eid, (u, v) in enumerate(edges):
        if not dsu.union(u, v):
            return eid
    return None

On the example it returns edge 5, which is (4, 1), the same edge DFS used as its back edge. Self-loops are handled for free, since find(u) == find(u). The second of two parallel edges is caught as well. The cost is close to O(E) for the whole stream, with O(V) memory and no adjacency list at all.

Union-find is the right tool when edges arrive over time and you must reject the one that would create a loop. That is the inner test of Kruskal's minimum spanning tree (see Kruskal's algorithm). It is also the "redundant connection" problem: find the edge whose removal turns the graph back into a tree. Its weakness is that it cannot tell you the rest of the cycle. It knows u and v share a root, not the path between them. When you need the path, run a BFS between u and v over the edges accepted so far, or switch to DFS.

BFS and the shortest cycle

Breadth-first search detects cycles with the same parent-edge rule as DFS. When BFS meets an already-discovered vertex through an edge other than the one that discovered the current vertex, a cycle exists. BFS earns its place for a different question, the shortest cycle (the girth). Run BFS from a source s. For every non-tree edge (u, v) you meet, dist[u] + dist[v] + 1 is the length of a closed walk through s, and it is an upper bound on some cycle's length. Taking the minimum over every source gives the exact girth of an unweighted undirected graph in O(V x E) time. That is fine for thousands of vertices and too slow for millions. For the plain yes/no question, BFS and DFS cost the same, and BFS needs no recursion workaround because it is iterative by nature. The traversal basics are in BFS and DFS.

Choosing a method

The last row matters. None of these methods works on directed graphs. In a directed graph, reaching a visited vertex is not enough. It must be on the current recursion path, which is why the directed version needs three colours. See Cycle Detection in Directed Graph for that algorithm.

Where it runs in production

Real systems apply this in a few recurring places. Network topology: a loop in a layer-2 Ethernet segment makes broadcast frames circulate indefinitely. Spanning-tree protocols exist precisely to block links until the active topology is a tree. A configuration or inventory checker that models switches and links as an undirected graph can flag a planned change that would create a loop before anyone applies it. Hierarchy validation: data that should form a tree (an org chart stored as undirected reporting links, a cable plan, a mesh of pipes that must not double back) can be validated with the E = V - C test on every write. Graph construction pipelines: Kruskal-style clustering and maze generation both reject cycle-closing edges with union-find. Circuit and flow analysis uses the cyclomatic number to count independent loops.

Failure modes

• Parent-vertex skipping on a multigraph. Two parallel links between the same pair of devices are a loop, and skipping "the parent" hides it. Skip the parent edge id, or deduplicate edges on purpose and document that choice.
• Self-loops ignored. Some adjacency builders drop (u, u) or add it once instead of twice. Decide whether a self-loop is a cycle in your domain, and test it explicitly.
• Only searching from vertex 0. Disconnected graphs hide cycles in other components. Always loop over every unvisited root.
• Recursion on deep graphs. Paths and long rings exhaust the call stack. Use the explicit-stack version anywhere input size is not tightly bounded; see iterative DFS with an explicit stack.
• Mixing directed and undirected semantics. Storing each undirected edge as two directed arcs and then running a directed algorithm reports a cycle on every edge.

What to do next

1. Write down whether your input is a simple graph or a multigraph, and whether duplicates and self-loops are real edges or noise.
2. If you only need yes or no and already compute components, use E = V - C and stop.
3. If you need the cycle, use the iterative DFS above with edge ids. Keep the parallel-edge, self-loop, tree and disconnected cases as unit tests.
4. If edges stream in, use union-find and log the rejected edge. Run a BFS over accepted edges when an operator needs the full loop.
5. Add a 200,000-vertex path or ring to your tests, so a later rewrite to recursion fails loudly.
6. Read the directed version next, then bridges to learn which edges lie on cycles.