EP03

EP03: Bach and Graph Connectivity

k-连通性, 割顶

▶ — Graph Theory

后续拓展

EP05 Turán's Theorem and Counterpoint EP06 Graph Coloring and Voice Assignment

小红书 Watch on 小红书

Overview

Bach’s Fugue in C Major (BWV 846) has four independent voices: soprano, alto, tenor, bass. Delete any one of them and the remaining three still form a coherent harmonic structure. Why? The mathematical answer is graph connectivity: the voice-structure of polyphonic music forms a 2-connected graph with no cut vertices, while homophonic music (melody + accompaniment) is at best 1-connected, with the melody as a potential cut vertex.

This episode develops the theory of graph connectivity — cut vertices, bridges, $k$ -connectivity — and applies it to a Bach chorale model. We also introduce Tarjan’s linear-time algorithm for finding cut vertices via depth-first search, and sketch the topological extension using simplicial complexes and Betti numbers.

中文: “复调音乐的’删不坏感'，并非偶然，而源于其分布式结构。”

Prerequisites

Basic graph theory: graphs, paths, cycles, connectivity
Depth-first search (DFS)
Motif networks (EP17) — chord/motif graphs as weighted directed graphs
Character networks (EP20) — cut vertex as “obligatory character”

Definitions

Definition 3.1 (Graph Connectivity)

An undirected graph $G = (V, E)$ is connected if for every pair of vertices $u, v \in V$ there exists a path from $u$ to $v$ .

The connected components of $G$ are its maximal connected subgraphs.

Definition 3.2 (Cut Vertex (Articulation Point))

A vertex $v \in V$ is a cut vertex (or articulation point) of a connected graph $G$ if the subgraph $G - v$ (obtained by deleting $v$ and all edges incident to $v$ ) is disconnected.

Equivalently, $v$ is a cut vertex if and only if there exist vertices $u, w \neq v$ such that every path from $u$ to $w$ passes through $v$ .

Definition 3.3 (Bridge)

An edge $e = \{u,v\} \in E$ is a bridge if the graph $G - e$ (obtained by deleting only the edge $e$ ) is disconnected.

Every bridge $e = \{u,v\}$ satisfies: $u$ is a cut vertex in $G - v$ and vice versa (unless one of them has degree 1, in which case $e$ is a pendant edge).

Definition 3.4 (k-Connectivity)

For $k \geq 1$ , a graph $G$ with $|V| > k$ is $k$ -connected if removing any set of fewer than $k$ vertices leaves $G$ connected. Formally:

\kappa(G) = \min\{|S| : S \subseteq V,\; G - S \text{ is disconnected or has fewer than 2 vertices}\}

is the vertex connectivity of $G$ . We say $G$ is $k$ -connected if $\kappa(G) \geq k$ .

Special cases:

$\kappa(G) \geq 1$ : connected (no vertex whose removal disconnects)
$\kappa(G) \geq 2$ : 2-connected — no cut vertices
$\kappa(G) \geq 3$ : 3-connected — no pair of vertices whose removal disconnects

Definition 3.5 (DFS Discovery and Finish Times)

In a depth-first search of a graph $G$ starting from vertex $s$ , each vertex $v$ receives:

Discovery time $d[v]$ : the step at which $v$ is first visited
Finish time $f[v]$ : the step at which all neighbors of $v$ have been explored

A back edge $\{u, v\}$ in an undirected DFS tree is an edge where $v$ is an ancestor of $u$ in the DFS tree (i.e., $d[v] < d[u]$ and $v$ was not processed via $u$ ).

Definition 3.6 (Low Value)

For each vertex $v$ in a DFS tree, define the low value:

\mathrm{low}[v] = \min\!\left(\{d[v]\} \cup \{d[w] : \{u,w\} \in E \text{ for some descendant } u \text{ of } v, \text{ and } \{u,w\} \text{ is a back edge}\}\right)

Informally, $\mathrm{low}[v]$ is the smallest discovery time reachable from the subtree rooted at $v$ using at most one back edge.

Definition 3.7 (Voice Graph of a Polyphonic Work)

Given a $k$ -voice polyphonic composition, define the voice graph $G_{\mathrm{voice}} = (V, E)$ where:

$V = \{v_1, \ldots, v_k\}$ : one vertex per voice (soprano, alto, tenor, bass)
$E$ : an edge $\{v_i, v_j\}$ is present if voices $i$ and $j$ form a consonant harmonic interval (third, fifth, sixth, octave) simultaneously at some point in the piece

In the weighted version, the weight $w(v_i, v_j)$ counts the number of beats at which $v_i$ and $v_j$ are in consonance.

Main Theorems

Theorem 3.1 (Tarjan's Cut Vertex Algorithm)

A non-root vertex $v$ in a DFS tree is a cut vertex of $G$ if and only if $v$ has a child $u$ in the DFS tree such that

\mathrm{low}[u] \geq d[v]

The root of the DFS tree is a cut vertex if and only if it has at least two children in the DFS tree.

This algorithm finds all cut vertices in $O(|V| + |E|)$ time.

Proof.

Correctness of the non-root condition:

Suppose $v$ is a non-root DFS vertex and $u$ is a child of $v$ in the DFS tree. The condition $\mathrm{low}[u] \geq d[v]$ means that no vertex in the subtree rooted at $u$ has a back edge to any proper ancestor of $v$ .

( $\Rightarrow$ ) If $\mathrm{low}[u] \geq d[v]$ for some child $u$ , then the subtree of $u$ cannot reach any ancestor of $v$ without going through $v$ . Hence removing $v$ disconnects the subtree of $u$ from the rest of the graph, so $v$ is a cut vertex.

( $\Leftarrow$ ) Suppose $v$ is a cut vertex. Let $C$ be a connected component of $G - v$ that does not contain $v$ ’s parent in the DFS tree. Pick any vertex $u$ of $C$ that was first reached from $v$ in the DFS (i.e., $u$ is in $v$ ’s DFS subtree). Since $C$ has no direct path to $v$ ’s parent (otherwise $v$ would not separate $C$ ), all paths from the subtree of $u$ to ancestors of $v$ pass through $v$ , meaning $\mathrm{low}[u] \geq d[v]$ .

Root case: The root has no parent; it is a cut vertex exactly when its removal separates its subtrees, which happens iff it has $\geq 2$ children.

Complexity: DFS runs in $O(|V| + |E|)$ . Computing $\mathrm{low}[v]$ for all vertices during the DFS adds no asymptotic overhead (one pass, bottom-up). $\square$

Visual: Trace DFS on a small example: vertices $\{A,B,C,D,E\}$ , edges $AB, BC, CA, CD, DE$ . Vertex $C$ has $d[C] = 3$ ; child $D$ ’s subtree can only reach $D$ and $E$ , so $\mathrm{low}[D] = d[D] = 4 \geq d[C] = 3$ . Hence $C$ is a cut vertex. Removing $C$ disconnects $\{D,E\}$ from $\{A,B\}$ .

Theorem 3.2 (Whitney's Theorem)

For any graph $G$ with $|V| \geq 2$ :

\kappa(G) \leq \kappa'(G) \leq \delta(G)

where $\kappa(G)$ is vertex connectivity, $\kappa'(G)$ is edge connectivity (minimum number of edges whose removal disconnects $G$ ), and $\delta(G) = \min_{v \in V} \deg(v)$ is the minimum degree.

Proof.

$\kappa'(G) \leq \delta(G)$ : Let $v$ be a vertex of minimum degree $\delta(G)$ . The $\delta(G)$ edges incident to $v$ form a cut set (removing them isolates $v$ ). Hence $\kappa'(G) \leq \delta(G)$ .

$\kappa(G) \leq \kappa'(G)$ : Given a minimum edge cut $F$ with $|F| = \kappa'(G)$ , we construct a vertex cut of size at most $|F|$ . For each edge $\{u,v\} \in F$ , choose one of its endpoints (say $v$ ) to include in a vertex cut $S$ . Removing $S$ separates the graph (since $F$ was a cut and each edge in $F$ has an endpoint in $S$ ). This argument may select the same vertex for multiple edges, so $|S| \leq |F|$ , giving $\kappa(G) \leq \kappa'(G)$ . $\square$

Remark: The bounds are tight but not always equal. The complete bipartite graph $K_{3,3}$ satisfies $\kappa = \kappa' = \delta = 3$ . The graph obtained from $K_4$ by subdividing one edge has $\kappa = 2 < \kappa' = 3 < \delta = 3$ .

Theorem 3.3 (Menger's Theorem)

For vertices $s \neq t$ in a graph $G$ , the maximum number of internally vertex-disjoint $s$ - $t$ paths equals the minimum size of a vertex cut separating $s$ from $t$ .

Consequently, $G$ is $k$ -connected if and only if every pair of distinct vertices is connected by at least $k$ internally vertex-disjoint paths.

Proof.

This is a special case of the max-flow min-cut theorem applied to the auxiliary network $N$ defined as follows:

Each vertex $v \in V \setminus \{s,t\}$ is split into $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}} \to v_{\mathrm{out}}$ of capacity 1.
Each undirected edge $\{u,v\}$ becomes two directed edges: $u_{\mathrm{out}} \to v_{\mathrm{in}}$ and $v_{\mathrm{out}} \to u_{\mathrm{in}}$ , each with capacity 1 (or $\infty$ if we only care about vertex cuts).
The source is $s_{\mathrm{out}}$ , the sink is $t_{\mathrm{in}}$ .

In this network, a flow of value $k$ corresponds to $k$ internally vertex-disjoint paths, and a minimum cut of value $k$ corresponds to a minimum vertex separator of size $k$ . The max-flow min-cut theorem then gives Menger’s result. $\square$

Prop 3.1 (Polyphony Is 2-Connected)

The voice graph of a Bach four-voice fugue is 2-connected (no cut vertices). The voice graph of a standard homophonic texture (single melody with chordal accompaniment) is at most 1-connected and typically has the melody as a cut vertex.

Proof.

(Empirical argument supporting the mathematical claim.) In a four-voice fugue such as BWV 846, every pair of voices forms at least one consonant interval during the piece (verified by score analysis). Moreover, every voice is in consonance with every other voice in multiple passages. Consequently, the voice graph is $K_4$ (the complete graph on 4 vertices), which has $\kappa(K_4) = 3$ . Even after removing one voice, the remaining three form $K_3$ , which is connected.

In homophonic texture, the accompaniment voices may only be in consonance with the melody but not with each other except through the melody. This produces a star graph $K_{1,3}$ with the melody at the center — a graph with $\kappa(K_{1,3}) = 1$ and the center as the unique cut vertex. $\square$

中文: “复调音乐是分布式结构，每个声部都与其他声部密切连接，形成高连通的网状拓扑，没有不可或缺的中心。”

Tarjan’s Algorithm: Worked Example

Consider $G$ with $V = \{0,1,2,3,4\}$ and edges $\{0,1\}, \{1,2\}, \{2,0\}, \{1,3\}, \{3,4\}$ .

DFS from vertex 0 (discovery order: 0,1,2 backtracks; 1 continues to 3,4):

Vertex	$d[v]$	$f[v]$	$\mathrm{low}[v]$
0	0	9	0
1	1	8	0
2	2	3	0 (back edge to 0)
3	4	7	4
4	5	6	4

Check cut-vertex condition:

Vertex 1: child 3 has $\mathrm{low}[3] = 4 \geq d[1] = 1$ . Cut vertex.
Vertex 3: child 4 has $\mathrm{low}[4] = 4 \geq d[3] = 4$ . Cut vertex.

Removing vertex 1 disconnects $\{3,4\}$ from $\{0,2\}$ . Removing vertex 3 disconnects $\{4\}$ . These are precisely the articulation points.

Extension: Simplicial Complexes and Betti Numbers

Definition 3.8 (Simplicial Complex of a Score)

Given a $k$ -voice piece, define a simplicial complex $\mathcal{K}$ where:

0-simplices: individual notes (pitch classes at time $t$ )
1-simplices: dyads (pairs of simultaneously sounding notes)
2-simplices: trichords (three simultaneously sounding notes)
$(k-1)$ -simplices: $k$ -note chords

The $n$ -th Betti number $\beta_n$ counts $n$ -dimensional “holes” in $\mathcal{K}$ . $\beta_0$ counts connected components, $\beta_1$ counts independent cycles.

中文: “传统的图只能捕捉两个音符之间的关系，但和弦是三个或更多音符的同时交互，这种高阶关系需要更高级的数学工具：单纯复形。”

The 2025 paper cited below used this approach to distinguish fugues from dances in Bach’s WTC. Fugues exhibit high $\beta_1$ (many harmonic cycles) while dances show simpler topology.

Musical Connection

音乐联系

Cut Vertices and Harmonic Syntax

In a chord-progression graph (vertices = chords, weighted directed edges = transition frequency), the dominant seventh chord V7 functions as a near-cut-vertex in common-practice tonality. Almost all progressions to the tonic I pass through V7, making it the bottleneck of harmonic syntax.

In Bach’s chorales, Rameau’s principle of fundamental bass predicts that V → I is the strongest directed edge. A chord-graph analysis of a Bach chorale corpus (e.g., the 371 harmonized chorales) reveals:

V7 (G7 in C major) has the highest betweenness centrality of any chord — it lies on the most shortest paths between other chords
The I–IV–V–I “loop” has no interior cut vertex (it is the backbone 3-cycle of the graph)
Chromatic chords (viio7, augmented sixths) appear as bridges: edges whose removal would disconnect remote key areas from the tonic region

This is why Wagner could exploit chromatic bridges so dramatically: by avoiding the V7 → I resolution (the strongest edge), he kept the harmonic graph in a perpetually “almost-disconnected” state, creating sustained tension.

中文: “从图论的连通性，到复调音乐的声部结构，数学再一次揭示了音乐的深层逻辑。”

Limits and Open Questions

Directed vs. undirected graphs: The voice graph model (Definition 3.7) is undirected, but chord-progression graphs are naturally directed. Directed connectivity (strong vs. weak connectivity) is a stronger notion: a directed graph is strongly connected if for every ordered pair $(u,v)$ there is a directed path from $u$ to $v$ . The harmonic syntax graph of a key is strongly connected within the diatonic scale but not across all chromatic chords.
Temporal dynamics: Graph connectivity is a static measure. A sliding-window analysis that recomputes $\kappa(G_t)$ at each time window $t$ reveals how connectivity evolves during a piece — tension arches correspond to drops in $\kappa$ .
Edge weights and weighted connectivity: Weighted $k$ -connectivity (where edge weights represent transition probabilities) uses flow-based generalizations of Menger’s theorem. The maximum weighted flow through the network gives a more musically meaningful notion of “structural importance.”
Simplicial homology and music: Computing Betti numbers for a Bach fugue requires building the full simplicial complex (Definition 3.8) and then computing the ranks of homology groups $H_n(\mathcal{K}, \mathbb{Z})$ . For large choral works, this is computationally feasible but the musical interpretation of $\beta_2$ (3-dimensional holes) remains open.

Conjecture (Polyphony Degree and Connectivity)

For a

k

-voice polyphonic work where every pair of voices forms at least one consonant interval, the voice graph contains

K_k

as a subgraph, so

\kappa(G_{\mathrm{voice}}) \geq k-1

. Conversely, the minimum connectivity of any

k

-voice homophonic texture is at most 1. This suggests a sharp connectivity threshold distinguishing polyphonic from homophonic texture, independent of the specific harmony used.

Academic References

Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.
Whitney, H. (1932). Congruent graphs and the connectivity of graphs. American Journal of Mathematics, 54(1), 150–168.
Menger, K. (1927). Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10, 96–115.
Tymoczko, D. (2011). A Geometry of Music. Oxford University Press. Ch. 2 (Harmonic progressions as graphs).
Bergomi, M. G., Baratè, A., & Di Fabio, B. (2015). Towards a topological fingerprint of music. Lecture Notes in Computer Science, 9067, 88–100.
Cantù, D., & Andreatta, M. (2025). Topological analysis of Bach’s Well-Tempered Clavier using simplicial homology. Journal of Mathematics and Music, 19(1), 1–22.
Diestel, R. (2017). Graph Theory (5th ed.). Springer. Ch. 3 (Connectivity).
Popoff, A., Andreatta, M., & Ehresmann, A. (2018). Relational poly-Klumpenhouwer networks for transformational and voice-leading analysis. Journal of Mathematics and Music, 12(1), 35–55.