Algebraic and Spectral Graph Theory

We argue by induction on $k$. For $k=1$, the number of walks of length $1$ from $v_i$ to $v_j$ is $1$ when $v_i$ and $v_j$ are adjacent and $0$ otherwise, so it is exactly $A_{ij}$ by [F1].

Assume the claim for some $k\ge 1$. Then $(A^{k+1}{)}_{ij}={\sum }_{r=1}^n(A^k{)}_{ir}{A}_{rj}$. By the inductive hypothesis, $(A^k{)}_{ir}$ counts the walks of length $k$ from $v_i$ to $v_r$, while [F1] makes $A_{rj}$ the indicator that the final edge $v_r{v}_j$ exists. Therefore the summand counts the length-$(k+1)$ walks from $v_i$ to $v_j$ whose last intermediate vertex is $v_r$, and summing over $r$ counts all such walks exactly once by [F2].

The base case and inductive step prove the claim for every $k\ge 1$.

For each vertex $v_i$, a walk of length $k$ from $v_i$ to itself is exactly a closed walk of length $k$ whose chosen start vertex is $v_i$, so [L1] makes $(A^k{)}_{ii}$ the number of such closed walks.

Summing step 1.1 over all vertices counts every closed walk of length $k$ exactly once for each of its chosen start vertices, and by [F1] that sum is $\mathrm{tr}(A^k)$. Hence the trace counts the closed walks of length $k$.

Order the vertices of $G$ as $v_1,\dots ,v_n$ and the vertices of $H$ as $\phi (v_1),\dots ,\phi (v_n)$. In these orders the adjacency matrices $A(G)$ and $A(H)$ have the same entries, because [F1] and [F2] say that the $(i,j)$ entry is $1$ in either matrix exactly when $v_i$ and $v_j$ are adjacent in $G$.

Since the two matrices are equal after a relabelling of the basis, they have the same characteristic polynomial and therefore the same spectrum by [F3]. This is exactly the claimed invariance.

Assume first that $G$ is bipartite with parts $X$ and $Y$. Let $D$ be the diagonal matrix whose $vv$ entry is $1$ on $X$ and $-1$ on $Y$. Then $D^{-1}=D$, and [F1] shows that every edge changes sign across the partition, so $DAD=-A$. Hence $A$ and $-A$ are similar and therefore have the same eigenvalues. By [F2], the spectrum is symmetric about $0$.

Conversely, assume the spectrum is symmetric about $0$. Because [F2] cites the real spectral theorem for the real symmetric matrix $A$, there is an invertible matrix $P$ with $P^{-1}AP=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)$. For every odd integer $r\ge 1$, this gives $P^{-1}{A}^{r}P=\mathrm{diag}({\lambda }_1^r,\dots ,{\lambda }_n^r)$, so [L3] yields $\mathrm{tr}(A^r)={\sum }_{i=1}^n{\lambda }_i^r=0$ after the odd powers cancel in symmetric pairs. By [L2], $G$ has no closed walk of odd length. An odd cycle would itself be an odd closed walk, so $G$ has no odd cycle. Therefore [L1] makes $G$ bipartite.

Steps 1.1 and 1.2 prove the two directions of the equivalence.

Let $\mathbf{1}$ be the all-ones vector. Then $R_A(\mathbf{1})=\frac{{\mathbf{1}}^{\mathsf{T}}A\mathbf{1}}{{\mathbf{1}}^{\mathsf{T}}\mathbf{1}}=\frac{{\sum }_{v\in V(G)}\mathrm{deg}(v)}{n}=\bar{d}(G)$, because ${\mathbf{1}}^{\mathsf{T}}A\mathbf{1}$ adds all row sums of $A$. By [L1], the largest adjacency eigenvalue is at least this Rayleigh quotient, so ${\lambda }_1(G)\ge \bar{d}(G)$. Hence $\rho (G)\ge \bar{d}(G)$ by [F2].

Every Gershgorin disk of $A$ is centered at $0$, because the diagonal of an adjacency matrix is zero, and its radius is the corresponding row sum, hence at most $\mathrm{\Delta }(G)$ by [F1]. Therefore [L2] implies $\mathrm{\mid }\lambda \mathrm{\mid }\le \mathrm{\Delta }(G)$ for every adjacency eigenvalue $\lambda$, so [F2] gives $\rho (G)\le \mathrm{\Delta }(G)$.

Combining steps 1.1 and 1.2 yields the stated bounds.

The $(i,i)$ entry of $B{B}^{\mathsf{T}}$ is ${\sum }_j{b}_{ij}^2$. By [F1], the term $b_{ij}^2$ is $1$ exactly when the edge $e_j$ is incident with $v_i$, and is $0$ otherwise. Therefore $(B{B}^{\mathsf{T}}{)}_{ii}$ is the number of edges incident with $v_i$, namely $\mathrm{deg}(v_i)=L_{ii}$ by [F2].

For $i\mathrm{\ne }r$, the entry $(B{B}^{\mathsf{T}}{)}_{ir}={\sum }_j{b}_{ij}{b}_{rj}$ receives a nonzero contribution only from edges incident with both $v_i$ and $v_r$. In a simple graph there is at most one such edge. If $v_i$ and $v_r$ are not adjacent, the sum is $0$. If they are adjacent, the unique common edge contributes $(1)(-1)$ or $(-1)(1)$, hence $-1$. So $(B{B}^{\mathsf{T}}{)}_{ir}=L_{ir}$ by [F2].

Steps 1.1 and 1.2 show that every entry of $B{B}^{\mathsf{T}}$ matches the corresponding entry of $L(G)$, so the matrices are equal.

For every $x\in {\mathbb{R}}^n$, [L1] gives $x^{\mathsf{T}}Lx=x^{\mathsf{T}}B{B}^{\mathsf{T}}x=(B^{\mathsf{T}}x{)}^{\mathsf{T}}(B^{\mathsf{T}}x)$. The right-hand side is a sum of squares of real numbers, so it is nonnegative.

Let $\mathbf{1}$ be the all-ones vector. Because each column of $B$ has one $1$ and one $-1$, [F1] implies that every column sum of $B$ is $0$, so $B^{\mathsf{T}}\mathbf{1}=0$. Using [L1] again gives $L\mathbf{1}=B{B}^{\mathsf{T}}\mathbf{1}=B0=0$.

Step 1.1 proves positive semidefiniteness, and step 1.2 proves that the all-ones vector lies in the kernel.

For a vector $x=(x_v{)}_{v\in V(G)}$, the Laplacian quadratic form is $x^{\mathsf{T}}Lx={\sum }_{\{u,v\}\in E(G)}(x_u-x_v{)}^2$, because expanding $x^{\mathsf{T}}(D-A)x$ groups the diagonal terms by degrees and subtracts each edge contribution twice. Therefore, if $Lx=0$, then [L2] gives $0=x^{\mathsf{T}}Lx$, so every summand vanishes and $x_u=x_v$ on every edge. Conversely, if $x$ is constant on every edge, then for each vertex $u$ every neighbor $v$ of $u$ satisfies $x_v=x_u$, so [F2] gives $(Lx{)}_u=\mathrm{deg}(u)x_u-{\sum }_{v\sim u}{x}_v=0$. Hence $Lx=0$.

By [F1], a function on $V(G)$ is constant on every edge exactly when it is constant on each connected component. By [L1], the indicator vectors ${\mathbf{1}}_{C_1},\dots ,{\mathbf{1}}_{C_r}$ are linearly independent and every vector constant on components is a linear combination of them. So step 1.1 shows that these indicator vectors form a basis of $\ker L$, and hence $\dim \ker L=r$.

The final equivalence with multiplicity of the eigenvalue $0$ follows from [L3], because $L$ is real symmetric.

If $G$ is connected, then [L1] says that the eigenvalue $0$ has multiplicity $1$, so the next Laplacian eigenvalue ${\mu }_2(G)$ is strictly positive. By [F1], the algebraic connectivity is positive.

If the algebraic connectivity is positive, then [F1] gives ${\mu }_2(G)>0$, so $0$ occurs only once in the Laplacian spectrum. By [L1], the number of connected components is therefore $1$, which means that $G$ is connected.

Steps 1.1 and 1.2 prove the two directions of the equivalence.

Write the columns of $A$ as $a_0,\dots ,a_{n-1}$ and the columns of $AB$ as $c_0,\dots ,c_{m-1}$. Then [F2] gives $c_j={\sum }_{r<n}{b}_{rj}{a}_r$ for each $j<m$. By multilinearity of the determinant from [F1], this gives $\det (AB)=\det (c_0,\dots ,c_{m-1})={\sum }_{r_0,\dots ,r_{m-1}<n}\left({\prod }_{j<m}{b}_{r_j,j}\right)\det (a_{r_0},\dots ,a_{r_{m-1}})$.

If some index repeats among $r_0,\dots ,r_{m-1}$, then the determinant term vanishes by alternation in [F1]. When $m>n$, every $m$-tuple has a repeated index, so all terms vanish and $\det (AB)=0$.

Assume now that $m\le n$. By step 2.1, the sum from step 1.1 may be restricted to tuples whose indices are all distinct. Such tuples are exactly the permutations of the $m$-element sets $S=\{s_0<\cdots <s_{m-1}\}$. Grouping together the $m!$ terms attached to one fixed $S$ gives ${\sum }_{\sigma \in S_m}\left({\prod }_{j<m}{b}_{s_{\sigma (j)}j}\right)\det (a_{s_{\sigma (0)}},\dots ,a_{s_{\sigma (m-1)}})=\det (A[S])\det (B[S])$, because permuting the chosen columns of $A[S]$ contributes the same sign that appears in the Leibniz expansion of $B[S]$. Summing over all $m$-element subsets $S$ proves the formula.

In the standard vertex order, the adjacency matrix of $K_n$ is $J-I$, where $J$ is the all-ones matrix, because [F1] makes every off-diagonal entry equal to $1$ and every diagonal entry equal to $0$. The all-ones vector $\mathbf{1}$ satisfies $J\mathbf{1}=n\mathbf{1}$, so $(J-I)\mathbf{1}=(n-1)\mathbf{1}$.

If $x$ is orthogonal to $\mathbf{1}$, then the coordinates of $x$ sum to $0$, so $Jx=0$. Hence $(J-I)x=-x$. The subspace ${\mathbf{1}}^{\perp }$ has dimension $n-1$, so $-1$ is an eigenvalue with multiplicity at least $n-1$; together with step 1.1 this accounts for all $n$ dimensions.

Therefore the eigenvalues of the adjacency matrix are exactly $n-1$ and $-1$ with the stated multiplicities, which is the spectrum by [F2].

Delete row $i$ from $B$ to obtain an $(n-1)\times \mathrm{\mid }E(G)\mathrm{\mid }$ matrix $B^{(i)}$. By [L1], the matrix $L^{(i)}$ obtained by deleting row $i$ and column $i$ from $L(G)$ is $L^{(i)}=B^{(i)}(B^{(i)}{)}^{\mathsf{T}}$. Applying [L3] gives $\det L^{(i)}={\sum }_{\mathrm{\mid }S\mathrm{\mid }=n-1}\det (B^{(i)}[S]{)}^2$, where $S$ ranges over all $(n-1)$-edge subsets of $E(G)$.

Fix such a set $S$, and let $G_S$ be the spanning subgraph with edge set $S$. If $G_S$ is disconnected, then the vertex-indicator vector of the component of $v_i$ gives a nonzero linear relation among the rows of $B^{(i)}[S]$, so $\det (B^{(i)}[S])=0$. If $G_S$ is connected, then $G_S$ has $n-1$ edges and is therefore a tree by [L2]. In that case choose the orientation of every edge of $G_S$ away from the root $v_i$ and order the nonroot vertices so that every parent precedes its children. In this order the matrix $B^{(i)}[S]$ is triangular with diagonal entries all $\pm 1$, hence $\det (B^{(i)}[S])=\pm 1$. Therefore $\det (B^{(i)}[S]{)}^2$ is $1$ when $S$ is the edge set of a spanning tree and $0$ otherwise.

Substituting step 1.2 into the sum of step 1.1 shows that $\det L^{(i)}$ counts exactly the spanning trees of $G$, namely $\tau (G)$ by [F1]. Since the right-hand side does not depend on $i$, every principal cofactor of the Laplacian is equal.

Expanding the characteristic polynomial $\det (tI-L)$ at $t=0$ shows that the coefficient of $t$ is $(-1{)}^{n-1}{\sum }_{i=1}^n\det L^{(i)}$. By [L1], this is $(-1{)}^{n-1}n\tau (G)$. On the other hand, [L2] gives $\det (tI-L)={\prod }_{j=1}^n(t-{\mu }_j)=t{\prod }_{j=2}^n(t-{\mu }_j)$, so the same coefficient of $t$ is $(-1{)}^{n-1}{\prod }_{j=2}^n{\mu }_j$. Therefore $n\tau (G)={\prod }_{j=2}^n{\mu }_j$.

If $G$ is $d$-regular, then $L=dI-A$. Applying [L3] to the polynomial $p(x)=d-x$ shows that the Laplacian eigenvalues are $d-{\lambda }_1,\dots ,d-{\lambda }_n$. Since ${\lambda }_1=d$, the zero Laplacian eigenvalue is $d-{\lambda }_1$, and substituting the others into step 1.1 gives $\tau (G)=\frac{1}{n}{\prod }_{j=2}^n(d-{\lambda }_j)$.

Steps 1.1 and 2.1 are exactly the two displayed formulas.

The graph $K_n$ is $(n-1)$-regular, so [L2] applies with $d=n-1$. By [L1], its nontrivial adjacency eigenvalues are all $-1$, hence $\tau (K_n)=\frac{1}{n}{\prod }_{j=2}^n((n-1)-(-1))=\frac{1}{n}{\prod }_{j=2}^{n}n=n^{n-2}$.

This matches the earlier Prüfer-code count in [L3], so the matrix-tree theorem gives a second proof of Cayley's formula.

Let ${\mathbf{1}}_S$ be the indicator vector of $S$, and put $x:={\mathbf{1}}_S-\frac{\mathrm{\mid }S\mathrm{\mid }}{n}\mathbf{1}$. Then $x\mathrm{\ne }0$ because $S$ is nonempty and proper, and $x$ is orthogonal to $\mathbf{1}$. Since $G$ is $d$-regular by [F1], the vector $\mathbf{1}$ is an adjacency eigenvector with eigenvalue $d$, so [L1] gives $x^{\mathsf{T}}Ax\le \lambda x^{\mathsf{T}}x$.