3.2.3. Labelling a graph
If we sign to all vertices of a label from a given label set of n
elements, then we speak about a labelled
graph.
Two labellings of a graph G of order n from the same set of n labels are considered distinct if they do not produce the same edge set.
Theorem 3.12. (Kirchoff, 1847,
Matrix-Tree Theorem): If G is a nontrivial labelled graph with adjacency
matrix A and degree matrix D, then the number of distinct
spanning trees of G is the value of any cofactor of the matrix .
We do not prove the theorem but illustrate with an easy example:

Now we count the cofactor
of element (2,3) of the matrix :
Consequently, there are 8 distinct spanning trees of the given graph G.
Figure 3.5. The distinct spanning trees of the given graph G.