Lagmental Vicfred

A DFS Tree Edge Is a Bridge When No Back Edge Escapes by Vicfred

The edge from v to a child u is a bridge exactly when u's subtree cannot reach v or an ancestor of v. The point is to make the formal expression readable enough to audit line by line.

The data

Connectivity asks how many vertices or edges must be removed to disconnect a graph \(G\). Depth-first search timestamps \(\operatorname{tin}(v)\) and low-link values \(\operatorname{low}(v)\) expose local cut structure.

$$ (v,u)\ \text{a DFS tree edge} $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ (v,u)\ \text{bridge}\Longleftrightarrow\operatorname{low}(u)>\operatorname{tin}(v) $$

Derivation

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ \left.\begin{aligned}\operatorname{low}(u)&>\operatorname{tin}(v)\\\Longrightarrow\quad\text{subtree}(u)&\not\rightsquigarrow v\text{ or an ancestor by a back edge}\end{aligned}\right\} $$

Invariant content

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad (v,u)\ \text{a DFS tree edge},\\[5pt] \mathsf{C}\;&:\quad (v,u)\ \text{bridge}\Longleftrightarrow\operatorname{low}(u)>\operatorname{tin}(v). \end{aligned} $$

Scope

Bridge and articulation criteria depend on DFS-tree relationships. Applying them to an arbitrary spanning tree gives false positives.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] (v,u)\ \text{bridge}\Longleftrightarrow\operatorname{low}(u)>\operatorname{tin}(v) \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Fri 26 January 2024. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.