Edge Smuggling

Let $H$ be the undirected graph after adding the hidden edge. Since $G$ is connected, a path already exists between the two endpoints of the added edge. Hence the added edge lies on a cycle of $H$ and belongs to one nontrivial biconnected component.

A nontrivial component here means a vertex-biconnected block other than a one-edge bridge block. The edges are partitioned into these blocks.

We use an st-ordering. Given a biconnected graph and one of its edges $(s,t)$, an ordering with the following properties exists and can be found in linear time:

• $s$ is first and $t$ is last.
• Every vertex other than $s,t$ has at least one earlier neighbor and at least one later neighbor.

In the first execution, compute the biconnected components of $H$.

For the block containing the added edge, choose its endpoints as $s,t$, compute an st-ordering, and orient every edge from the earlier endpoint to the later endpoint. Inside this block, only $s$ has internal indegree $0$, and only $t$ has internal outdegree $0$. The edge from $s$ to is exactly the added edge.

For every other nontrivial block, choose an arbitrary edge $(s,t)$. Compute an st-ordering, orient every other edge from the earlier endpoint to the later endpoint, and reverse only the chosen edge to point from $t$ to $s$. Every internal vertex already has both an incoming and an outgoing edge by the st-ordering property. The reversed edge gives $s$ an incoming edge and gives $t$ an outgoing edge. Thus every vertex of this block has positive internal indegree and positive internal outdegree.

Bridge edges may be oriented arbitrarily. In the second execution, biconnected components can be recomputed after ignoring directions, so one-edge bridge blocks are simply ignored.

In the second execution, compute indegrees and outdegrees using only the edges inside each nontrivial block. Exactly one block has one vertex $s$ of internal indegree $0$ and one vertex $t$ of internal outdegree $0$. The edge $s\to t$ in this block is the added edge.

Permuting vertex and edge labels preserves biconnected components and all internal degree properties, so the edge is always recoverable.

Tarjan's algorithm and a linear-time st-ordering algorithm give $O(N+M)$ time and $O(N+M)$ memory in each execution.