Prove that a graph cannot have EXACTLY two distinct spanning trees.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Welcome to MSE! Users are more likely to offer aid if you provide evidence that you have made an attempt in good faith to solve the problem by yourself. In addition, we can offer more targeted aid if you specify previous attempts you have made, as then we may be able to identify where you are struggling. For more on how to ask questions on this site, please visit math.stackexchange.com/help/asking. $\endgroup$– Gyu Eun LeeCommented Mar 20, 2015 at 6:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
I assume you mean simple graphs, not true for multi-graphs.
The union of the two spanning trees contains a cycle (contains too many edges to be a tree), cycles have length greater than $2$. Removing any edge from a cycle leaves a connected graph, so the union of the two spanning trees has at least $3$ spanning trees, each of which is a spanning tree for the original graph.
answered Mar 20, 2015 at 4:37
-
$\begingroup$ So now there are 3 spanning trees. Then what? $\endgroup$ Commented Mar 20, 2015 at 5:45
-
1$\begingroup$ @dalastboss: Nothing more is needed. $\endgroup$ Commented Mar 20, 2015 at 8:01
-
-
1$\begingroup$ I think your exposition is a little bit too terse. Call the edges of the cycle $e_1,e_2,\dots,e_n.$ It's not enough to say that $G-e_i$ is connectred and therefore has a spanning tree $T_i,$ because the trees $T_i$ are not necessarily distinct. It would be clearer to say that there is a spanning tree $T_i$ which omits the edge $e_i$ but contains the edges $e_j$ for $j\ne i.$ $\endgroup$– bofCommented Nov 26, 2015 at 5:27