For example a Cycle Graph C200 has only 1 spanning tree right?
Because adding just one edge to a spanning tree will create a cycle?
[Math] For a Cycle Graph is there only one Spanning tree
graph theory
Related Solutions
The claim is false.
Consider a graph $G$ with points $a,b,c,d,e$ and edges $(a,b),(b,c),(c,d),(d,e),(e,a),(a,d)$ where all edges have weight 1, except $(a,b)$ and $(a,e)$ which have weight 100. Then there is only one minimum spanning tree, namely $(b,c),(c,d),(d,e),(a,e)$.
If instead the claim was the following: "If a graph $G$ is a cycle, and two of the edges $e_1$ and $e_2$ have weight $w$ which is the maximum weight in $G$, then there are at least two different minimum spanning trees in $G$"
Then the claim is true. Consider some spanning tree $T$ in $G$. Since $T$ is spanning, one of the edges, lets say $e_1$ with weight $w$ must be in $T$. Now consider a new tree $T' = T - e_1 + e_2$. Now one can easily show that $T'$ is also spanning and has the same weight as $T$.
The proof is not valid because it fails to prove that the graph is acyclic. The non sequitur is in the following:
$\dots$just remove that edge that created a cycle, then it since that results in a graph with no cycles
Notice that the statement doesn't follow. Also, notice that adding an edge to any connected graph will create a cycle. You must use the fact that exactly $1$ cycle is generated as a result.
Hint: Argue by contradiction. Assume the graph has a cycle. When you connect two vertices of the cycle, how many cycles are created?
Best Answer
Technically, $C_n$ will have $n$ spanning trees ($n$ choices for the edge you you delete). But they are all isomorphic (paths of length $n-1$), so it depends on whether you want to consider them as distinct or the same.