Finding spanning trees in a graph

Question

I have a graph which consists of $V(G)={1,2,3,4,5,6,7}$ and the edge set $E(G)={14,42,25,53,45,46,57,67}$. This graph has one triangle and one 4-cycle (the triangle and 4-cycle share an edge), and I have to find all the spanning trees. I think that there are $3 \cdot 4 = 12$ because in both of these cycles I can choose to omit an edge, and there are 3 choices in the triangle, and 4 in the 4-cycle. Does this make any sense?

Answer 1

I count $11$. An $n$-vertex spanning tree has $n-1$ edges; here $n=7$ so we need to delete $2$ edges.

In the triangle $245$, we must delete one edge:

• If it's 24, then the other edge we delete can be 45, 46, 57, or 67.
• If it's 25, then the other edge we delete likewise can be 45, 46, 57, or 67.
• If it's 45, it can be 24, 25, 46, 57, or 67, but we've already counted 24 and 25.

Thus we get 11 in total, these are drawn below:

Answer 2

First of all, we agree on omitting $2$ edges in order to have the spanning trees. I think since there is a mutual edge for 3-cycle and 4-cycle, the answer may be $3 \cdot 4-1 = 11$ because when you choose one edge from 3-cycle and one edge from 4-cycle, you have to eliminate the case when you choose the mutual edge for both cycles, which is as same as omitting 1 edge and the remaining graph is obviously not a spanning tree. That's why I think your way of thinking makes sense but needs a small correction.