Unit 5: Algebraic Graph Theory: Incidence, Circuit, Cut-Set & Laplacian Matrices

1. The Vertex-Edge Incidence Matrix

Let $G = (V, E)$ be a graph with $n$ vertices $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges $E = \{e_1, e_2, \dots, e_m\}$.

Definition 5.1 (Incidence Matrix $A(G)$): The incidence matrix of $G$ is an $n \times m$ matrix $A(G) = (a_{ij})$ defined by:

If $G$ is an oriented (directed) graph:

Structural Observations:

1. Every column of $A(G)$ in a simple graph contains exactly two non-zero entries (corresponding to the two endpoints of that edge).
2. The sum of entries in row $i$ is the degree of vertex $v_i$: $\sum_{j=1}^m a_{ij} = \deg(v_i)$.
3. In the directed incidence matrix, every column sums to zero: $\sum_{i=1}^n a_{ij} = 0$.

2. Rank of the Incidence Matrix

Theorem 5.1 (Rank of $A(G)$): Let $G$ be a graph with $n$ vertices and $\omega(G)$ connected components. The rank of the incidence matrix over the field $\mathbb{R}$ (and over $\mathbb{F}_2$) is:

In particular, if $G$ is connected, $\text{rank}(A) = n - 1$.

Complete Proof (for connected graph):

Summing all rows of the directed incidence matrix yields the zero row:

Thus the $n$ rows are linearly dependent, so $\text{rank}(A) \le n - 1$. Now suppose a linear combination of rows vanishes: $\sum_{i=1}^n c_i A_{i, \cdot} = \mathbf{0}^T$. For any edge $e_j = (v_p, v_q)$, the $j$-th column has $+1$ at $p$ and $-1$ at $q$. Thus:

Since $G$ is connected, we can trace a path between any two vertices, implying $c_1 = c_2 = \dots = c_n = c$. Therefore, the only linear relation among the rows is $\sum A_{i, \cdot} = \mathbf{0}$. Any choice of $n - 1$ rows is linearly independent! Hence $\text{rank}(A) = n - 1$. $\blacksquare$

Definition 5.2 (Reduced Incidence Matrix $A_f$): The $(n - 1) \times m$ matrix obtained by deleting any single row from $A(G)$ is called the reduced incidence matrix $A_f$. The deleted row corresponds to the reference (datum) vertex.

1. The Circuit Matrix $B(G)$

Definition 5.3 (Circuit Matrix $B(G)$): Let $G$ have $m$ edges and let $q$ be the total number of simple circuits in $G$. The circuit matrix $B(G) = (b_{ij})$ is a $q \times m$ matrix defined by:

Over $\mathbb{R}$ with oriented circuits, $b_{ij} = \pm 1$ depending on whether the orientation of $e_j$ agrees with the orientation of circuit $C_i$.

2. The Fundamental Circuit Matrix $B_f$

Let $T$ be a spanning tree of connected graph $G$. Number of branches $= n - 1$. Number of chords $= \mu = m - n + 1$ (the cyclomatic number). Each chord $e \in E \setminus E(T)$ defines a unique fundamental circuit.

Definition 5.4 (Fundamental Circuit Matrix $B_f$): The fundamental circuit matrix $B_f$ relative to spanning tree $T$ is the $\mu \times m$ submatrix of $B$ corresponding to the $\mu$ fundamental circuits. Arranging the columns such that chords appear first and tree branches appear second:

where $I_\mu$ is the $\mu \times \mu$ identity matrix (each fundamental circuit contains exactly its own chord).

Theorem 5.2 (Rank of the Circuit Matrix): For any graph $G$ with $n$ vertices, $m$ edges, and $\omega$ components:

Proof:

Since $B_f$ contains the identity block $I_\mu$ of order $\mu = m - n + 1$, its rows are linearly independent over $\mathbb{F}_2$. Thus $\text{rank}(B_f) = \mu$. Since any cycle in $G$ can be expressed as a linear combination (symmetric difference / ring sum) of fundamental circuits, the row space of $B_f$ spans the row space of $B$. Therefore, $\text{rank}(B) = \mu(G)$. $\blacksquare$

1. The Cut-Set Matrix $C(G)$ and Fundamental Matrix $C_f$

Definition 5.5 (Cut-Set Matrix $C(G)$): Let $G$ have $m$ edges and let $p$ be the total number of cut-sets in $G$. The cut-set matrix $C(G) = (c_{ij})$ is a $p \times m$ matrix where:

Relative to a spanning tree $T$, each of the $n - 1$ branches defines a fundamental cut-set. Ordering edges as chords first ($E \setminus E(T)$) and tree branches second ($E(T)$):

where $I_{n-1}$ is the identity matrix corresponding to the $n - 1$ branches.

Theorem 5.3 (Rank of Cut-Set Matrix):

2. The Orthogonality Relationships

The interaction between the cycle space and the cut space represents one of the most elegant dualities in linear algebra:

Theorem 5.4 (Orthogonality of Incidence, Circuit and Cut-Set Matrices): In any graph $G$:

1. $A \cdot B^T \equiv 0 \pmod 2 \quad (\text{and } A \cdot B^T = 0 \text{ for directed graphs})$.
2. $B \cdot C^T \equiv 0 \pmod 2 \quad (\text{and } B \cdot C^T = 0 \text{ for directed graphs})$.
3. For the fundamental matrices partitioned as $B_f = \begin{bmatrix} I_\mu & B_{12} \end{bmatrix}$ and $C_f = \begin{bmatrix} C_{11} & I_{n-1} \end{bmatrix}$:

Proof:

1. $A B^T = 0$: The $(i, j)$-th entry of $A B^T$ is the dot product of row $i$ of $A$ (vertex $v_i$) and row $j$ of $B$ (circuit $C_j$).

If $v_i \notin C_j$, the dot product is 0. If $v_i \in C_j$, circuit $C_j$ contains exactly two edges incident with $v_i$. In the directed case, one edge enters $v_i$ ($-1$) and one departs ($+1$), so $(+1)(+1) + (-1)(+1) = 0$. In modulo 2, $1 + 1 \equiv 0 \pmod 2$. Thus $A B^T = 0$.

2. $B C^T = 0$: By Theorem 4.3, every cycle and every cut-set share an even number of edges.

The dot product counts the number of shared edges modulo 2, so $B C^T \equiv 0 \pmod 2$.

3. Relation between $B_{12}$ and $C_{11}$:

Therefore:

1. The Adjacency Matrix

Definition 5.7 (Adjacency Matrix $A(G)$): Let $G = (V, E)$ be a simple graph with $V = \{v_1, \dots, v_n\}$. The adjacency matrix $A(G) = (a_{ij})$ is the $n \times n$ symmetric matrix:

Since $G$ is undirected with no self-loops, $a_{ii} = 0$ and $A = A^T$.

2. Walk Counting Theorem via Matrix Powers

Theorem 5.5 (Walk Counting via $A^k$): Let $A$ be the adjacency matrix of a graph $G$. The $(i, j)$-th entry of the $k$-th matrix power $A^k$, denoted $(A^k)_{ij}$, is equal to the number of distinct walks of length $k$ from vertex $v_i$ to vertex $v_j$ in $G$.

Complete Proof (by induction on $k$):

• Base Case ($k = 1$): $(A^1)_{ij} = a_{ij}$, which is $1$ if an edge exists (a walk of length 1) and $0$ otherwise. Holds.
• Inductive Step: Assume $(A^{k-1})_{ir}$ equals the number of walks of length $k - 1$ from $v_i$ to $v_r$.

By definition of matrix multiplication:

Any walk of length $k$ from $v_i$ to $v_j$ consists of a walk of length $k - 1$ from $v_i$ to some vertex $v_r$, followed by the single edge $\{v_r, v_j\}$. If $\{v_r, v_j\} \in E$, then $a_{rj} = 1$, and there are $(A^{k-1})_{ir}$ such extensions. If $\{v_r, v_j\} \notin E$, then $a_{rj} = 0$, contributing 0 walks. Summing over all possible penultimate vertices $v_r \in V$ gives the total number of $v_i$-$v_j$ walks of length $k$. $\blacksquare$

Corollary 5.5.1 (Triangle Formula via Trace): The number of triangles in a simple graph $G$ is given by:

where $\lambda_1, \dots, \lambda_n$ are the eigenvalues of $A(G)$.

Proof:

$(A^3)_{ii}$ is the number of closed walks of length 3 starting and ending at $v_i$. Each triangle on vertices $\{u, v, w\}$ gives rise to 2 directed traversal directions ($u \to v \to w \to u$ and $u \to w \to v \to u$) and can start at any of its 3 vertices ($3 \times 2 = 6$ closed walks per triangle). Summing over all vertices: $\text{Tr}(A^3) = 6 \times (\text{triangles})$. $\blacksquare$

1. The Graph Laplacian Matrix

Definition 5.8 (Laplacian Matrix): Let $G$ be a simple graph on $n$ vertices. Let $D(G) = \text{diag}(\deg(v_1), \dots, \deg(v_n))$ be the diagonal degree matrix. The Laplacian matrix of $G$ is:

Component-wise:

Theorem 5.6 (Properties of the Laplacian):

1. $L = A_{\text{dir}} A_{\text{dir}}^T$, where $A_{\text{dir}}$ is the directed incidence matrix.
2. $L$ is symmetric and positive semi-definite ($x^T L x = \sum_{\{u, v\} \in E} (x_u - x_v)^2 \ge 0$).
3. The vector of all ones $\mathbf{1} = (1, 1, \dots, 1)^T$ satisfies $L \mathbf{1} = \mathbf{0}$, so $\lambda_1 = 0$ is always an eigenvalue.
4. The multiplicity of the eigenvalue $0$ equals the number of connected components $\omega(G)$.
5. The second smallest eigenvalue $\lambda_2(G)$ is the algebraic connectivity (Fiedler value).

2. Kirchhoff's Matrix Tree Theorem

Gustav Kirchhoff proved in 1847 that the Laplacian matrix encodes the exact number of spanning trees in a graph:

Theorem 5.7 (Kirchhoff's Matrix Tree Theorem, 1847): Let $G$ be a connected simple graph on $n$ vertices, and let $L(G)$ be its Laplacian matrix. For any choice of indices $i, j \in \{1, 2, \dots, n\}$, let $L(i, j)$ denote the submatrix obtained by deleting row $i$ and column $j$ from $L$. Then the total number of spanning trees of $G$, denoted $\tau(G)$, is given by:

That is, every cofactor of the Laplacian matrix $L$ is equal to $\tau(G)$. Furthermore, in terms of non-zero Laplacian eigenvalues $0 < \lambda_2 \le \dots \le \lambda_n$:

Proof using the Cauchy-Binet Formula:

Let $A_f$ be the reduced incidence matrix obtained by deleting row $i$ from $A_{\text{dir}}$. Then $L(i, i) = A_f A_f^T$. By the Cauchy-Binet Formula:

where $A_f|_S$ is the $(n - 1) \times (n - 1)$ submatrix of $A_f$ with columns indexed by $S$. By Theorem 5.1 and unimodularity of trees:

Therefore: