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.