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

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.

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.

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.

There is also Kirchhoff's theorem. You take the Laplacian matrix of the graph (degree matrix - adjacency matrix), delete an arbitrary row and its corresponding column, and then find the determinant of the matrix. The value of the determinant will be the number of spanning trees for the graph.

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.