22
$\begingroup$

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.

  • 0
    @AustinMohr Hi, sorry, like I said, first post. Yes, I am trying to find the amount of spanning trees for a fixed, labeled graph.2011-12-13

7 Answers 7

19

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.

  • 0
    For future readers: for larger graphs, the Kirchoff theorem as answered below, and also as described in the linked pdf is a super-fast way to calculate the spanning tree count. You might need to use a version of determinant calculation that returns logarithm though to avoid overflow.2014-02-08
11

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.

6

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.

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.

  • 2
    It is worth noting that the number of spanning trees can be computed using linear algebra and the Tutte polynomial cannot.2012-03-24
-2

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

  • 0
    As @utdiscant mentions, there is one one complete graph on $n$ vertices. Cayley's formula, which is the fact mentioned here, can be deduced from the Matrix Tree Theorem Gerry mentions, but there are other more combinatorial proofs, e.g., the one by Joyal that can be found here. http://math.stackexchange.com/a/93421/215852012-03-24
-3

Number of spanning tree with number of nodes $n$ equal to $n^{n-2}$ for $n\geq2$ where $n$ is nodes

  • 1
    Also t$h$at formula is for *complete* labelled $g$raphs only.2015-04-02
-4

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

  • 0
    That applies only to the complete graph2017-06-02