NumberOfSpanningTrees(G) returns the number of labeled spanning trees of the graph G.

The strategy is to evaluate the determinant of a certain matrix related to the graph. (See Introduction to Graph Theory, by Douglas B. West)

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{K3}≔\mathrm{CompleteGraph}\left(3\right)$

$\mathrm{K3}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 3\; vertices\; and\; 3\; edges}$

$\mathrm{NumberOfSpanningTrees}\left(\mathrm{K3}\right)$

$3$

$\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$

$\mathrm{K4}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 6\; edges}$

$\mathrm{NumberOfSpanningTrees}\left(\mathrm{K4}\right)$

$16$