Finding the number of Spanning Trees of a Graph $G$

Question

This is my first question on the Mathematics StackExchange site, so please do tell me if I have not adhered to any conventions in this post.

Ok, so if I have a graph $G$, with say $6$ vertices and $7$ Edges, how would I determine how many possible spanning tree's are there?

I know this is probably a very simple question, but I am very new to Graph Theory.

Thanks.

Answer 1

One of my favorite ways of counting spanning trees is the contraction-deletion theorem. For any graph $G$, the number of spanning trees $\tau(G)$ of $G$ is equal to $\tau(G-e) + \tau(G / e)$, where $e$ is any edge of $G$, and where $G-e$ is the deletion of $e$ from $G$, and $G/e$ is the contraction of $e$ in $G$. This gives you a recursive way to compute the number of spanning trees of a graph.

Another rule, is that if you have a graph with a cut-vertex (a vertex which removal would separate the graph), then the number of spanning trees can be computed on each side of the cut-vertex, and then multiplied together.

There are some more examples of rules, for complete graphs, complete bipartite graphs and others in Section 5.2 here http://www.student.dtu.dk/~dawi/01227/01227-GraphTheory.pdf. It also contains an appendix (D) of small graphs and their number of spanning trees, which is useful if you use the contraction-deletion theorem.

Answer 2

There's no simple formula for the number of spanning trees of a (connected) graph that's just in terms of the number of vertices and edges. However, if you can compute the Tutte polynomial of the graph and then evaluate it at the point $(1,1)$, that's equal to the number of spanning trees.

Answer 3

The Matrix-Tree Theorem gives you a formula for the number of spanning trees. Of course, you must know more than just the number of vertices and the number of edges - after all, there are graphs with 6 vertices, 7 edges, and no spanning trees at all.

Answer 4

Yes there is. If it is a complete graph, and it must be a complete graph, the number of spanning trees is $n^{n-2}$ where $n$ is the number of nodes. For instance a comple graph with $5$ nodes should produce $5^3$ spanning trees and a complete graph with $4$ nodes should produce $4^2$ spanning trees.I do not know of a complete graph with $6$ nodes and $7$ edges. Is there such a graph? John Oke

Answer 5

$n^{n-2}$, it's called cayley's formula