Lesson 5

It turns out there is also an analytical formula for \(\tau(G)\). For it, we will need the Kirchhoff matrix (also known as the Laplacian matrix or Laplacian) of the graph \(G\). This is the matrix \(L \in \mathbb{Z}^{n \times n}\), where the cell \([i,i]\) (for all \(i \in [n]\)) contains the degree of vertex \(i\), the cell \([i,j]\) contains \(-1\) if \(\{i,j\} \in E\), and zero otherwise. Slightly differently: \(L=D-A\), where \(D\) is the matrix with vertex degrees on the diagonal, and \(A\) is the adjacency matrix of the graph.

Let \(G'\) be an arbitrary orientation of the graph \(G\) (each undirected edge \(\{i,j\}\) is replaced with a directed edge \((i,j)\)), and \(I\) be its incidence matrix: \(I \in \{-1,0,1\}^{n \times m}\), where in the \(k\)-th column, there is \(1\) in the row corresponding to the start of the \(k\)-th edge, and \(-1\) in the row corresponding to the end of that edge.

It is easy to see that \(L=II^{T}\). Indeed, \((II^{T})[i,j]\) equals the product of the \(i\)-th and \(j\)-th rows of \(I\). If \(i=j\), then in such a product, each edge adjacent to vertex \(i\) contributes one to the total sum. If \(i \neq j\), then the result is \(-1\) if \(\{i,j\} \in E\), and zero otherwise.