# Prove that no graph has exactly $2$ spanning trees.

This question is why I must go second time to the final exam in discrete mathematics.

The original question was:

For which $$n$$ exists a graph with $$n$$ spanning trees?

I know, that for $$n > 2$$ there exists a graph with $$n$$ spanning trees, because if we take $$C_3$$, which is a cycle with $$3$$ vertices, it has exactly $$3$$ spanning trees. Cycle on $$4$$ vertices has $$4$$ spanning trees and so on. I know that if a graph is not connected, than it has $$0$$ spanning trees, and if I have a graph on $$1$$ vertex, it has exactly $$1$$ spanning tree.

So the question remains, how do I prove, that no graph exists, which has exactly $$2$$ spanning trees.

• To be clear: What is your definition of "skeleton"? (From context, it seems you might mean what I know as "spanning tree" (a tree (cycle-free graph) that covers every vertex). I've only used "skeleton" in the sense of describing the vertex-and-edge graph of a polygon or polyhedron.) And are there any tacit assumptions about the graph? For instance must it be "simple" (at most one edge between two vertices)? (If not, then why won't your $C_n$ argument work for $n=2$, the graph with two vertices joined by two "parallel" edges?)
– Blue
Jan 4 at 12:53
• Exactly, I am sorry for the inconvenience, I am studying in Czech, I am a Hungarian, so it is sometimes hard for me to translate the terms even to my native language... Making a change to the question. Jan 4 at 13:01
• Have you tried to use induction on $n$? Jan 4 at 13:16
• @Norbi I think induction will do the job. I suggest that you try it out and if you get stuck, you can update your question to get some help. Jan 4 at 13:28
• It seems to me that there is no problem here. If a graph is not connected, it has no spanning tree. If the graph is connected and has no cycles, then it is a tree. If a connected graph has a cycle, then it has at least three spanning trees. Or did I not understand the question? Jan 4 at 14:18

1. If a graph is not connected, then it has $$0$$ spanning trees.
3. If graph $$G$$ is connected and has cycles, then it has a spanning tree $$T$$, which is obtained by removing some edges of $$G$$. Let $$e$$ be an edge of graph $$G$$ which is not included in the tree $$T$$. Then the graph $$T+e$$ has exactly one cycle. This cycle has at least two more edges besides $$e$$. Let these edges be $$e'$$ and $$e''$$. Then $$T'=T+e-e'$$ and $$T+e-e''$$ are ostensive trees of $$G$$. Thus we have at least three different spanning trees $$T$$, $$T'$$, $$T''$$ of graph $$G$$.