I have a problem. I am trying to count all the spanning trees in a graph(it doesn't have multi edges). I know that there is Kirchhoff's theorem, which lets me count it in quite an easy way, but I prefer a solution which uses cycles in this graph.
I tried to figure out how cycles affect the number of spanning trees, and I have found that when there is a cycle(without additional edges) we can simply delete one of the edges, and we will get a spanning tree. When there are n cycles jointed just by one node, we can just multiply the numbers of edges in every cycle and that is our result. The problem is when two cycles are jointed with more than just one node(for example 1 or 3 edges). I was trying to write an equation, which will let me count this number, and the only thing I got is c1*c2-s^2, where c1 is a size of cycle nr. 1, c2 is a size of cycle nr.2 and s is the number of their common edges. However it doesn't work in some cases. I attach an example below: complete graph
We know that the number of spanning trees in a complete graph is n^(n-2), so we know that it has 16 possible spanning trees. However my algorithm finds 20 of them. Here is why:
I find 3 cycles: (3,4,2),(4,2,1), and (3,4,2,1). then I just use my equation for cycle nr 1 and 2 (3* 3-1), which gives me 8, and at the end I use it one more time with the last cycle (8*3-4 [it has 2 common edges]) which gives me 20. I also have to add that my cycle finding algorithm does not always find a simple cycle.
Could somebody tell me where the mistake is, and how to fix it? Thanks in advance.