Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. Jack Hunt

share|improve this question
    
Do you mean that you have a single fixed graph that happens to have six vertices and seven edges, or do you want to sum over all graphs with six vertices and seven edges? In the former, it will depend on the particular configuration of the edges, so you will need to give more information. Also, are your graphs labeled or unlabeled? –  Austin Mohr Dec 13 '11 at 0:19
    
@AustinMohr Hi, sorry, like I said, first post. Yes, I am trying to find the amount of spanning trees for a fixed, labeled graph. –  VisionIncision Dec 13 '11 at 12:30

6 Answers 6

up vote 10 down vote accepted

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.

share|improve this answer
1  
This notes of graph theory is so great. But, do you know what packages and fonts were used in latex, to generate the PDF? –  d555 Feb 3 at 22:27
1  
Yes, I am one of the two authors (David). I have uploaded the main LaTeX files (and the chapter about spanning trees) here: dropbox.com/s/j1amlwqjk1x13cc/graphnotes.zip Basically, it is a somewhat customised Memoir template, and all figures are made with TikZ. –  utdiscant Feb 4 at 13:37
    
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. –  ron Feb 8 at 22:10

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.

share|improve this answer

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.

share|improve this answer
2  
It is worth noting that the number of spanning trees can be computed using linear algebra and the Tutte polynomial cannot. –  Louis Mar 24 '12 at 15:35

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.

share|improve this answer

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

share|improve this answer
1  
A complete graph is a graph where every pair of vertices is joined by an edge, thus the number of edges in a complete graph is $\frac{n(n-1)}{2}$. This gives, that the number of edges in THE complete graph on 6 vertices is 15. –  utdiscant Mar 24 '12 at 15:16
    
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. math.stackexchange.com/a/93421/21585 –  Louis Mar 24 '12 at 15:33

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.