Lagmental Vicfred

Articulation Points Separate DFS Child Subtrees by Vicfred

tags: mathematics, connectivity, bridges, Menger theorem

A nonroot vertex is an articulation point when one child subtree cannot climb above it. This is a compact note, but the quantifiers and hypotheses stay on the page.

Definitions first

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\ne\text{root} $$

The formulas should not be merged too early. The datum \(\mathsf D\), the conclusion \(\mathsf C\), and the bridge \(\Longrightarrow\) have three different logical jobs.

$$ v\ \text{articulation}\Longleftrightarrow\exists u\ \text{child of }v:\operatorname{low}(u)\ge\operatorname{tin}(v) $$

A small case in full

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ v=\text{root}\Longrightarrow v\ \text{articulation}\Longleftrightarrow\#\operatorname{children}_{\mathrm{DFS}}(v)\ge2 $$

The reusable statement

The aligned summary deliberately puts the datum and conclusion on different rows. Mathematically, this is the distinction between specifying an object and proving a property of it.

$$ \begin{aligned} \mathsf{D}\;&:\quad v\ne\text{root},\\[5pt] \mathsf{C}\;&:\quad v\ \text{articulation}\Longleftrightarrow\exists u\ \text{child of }v:\operatorname{low}(u)\ge\operatorname{tin}(v). \end{aligned} $$

A nearby false statement

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\ \text{articulation}\Longleftrightarrow\exists u\ \text{child of }v:\operatorname{low}(u)\ge\operatorname{tin}(v) \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Sat 09 June 2018. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.