2
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ 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?) $\endgroup$
    – Blue
    Jan 4 at 12:53
  • $\begingroup$ 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. $\endgroup$
    – Norbi
    Jan 4 at 13:01
  • 1
    $\begingroup$ Have you tried to use induction on $n$? $\endgroup$
    – frabala
    Jan 4 at 13:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – frabala
    Jan 4 at 13:28
  • 6
    $\begingroup$ 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? $\endgroup$
    – kabenyuk
    Jan 4 at 14:18

1 Answer 1

2
$\begingroup$

Then here is more detailed reasoning that there is no simple graph that has exactly two spanning trees.

  1. If a graph is not connected, then it has $0$ spanning trees.

  2. If the graph is connected and has no cycles then the graph is a tree. In this case the graph has exactly one spanning tree. This tree is the graph itself.

  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$.

Since any graph with non-empty set of vertices has one of these three types, we proved that there is no simple graph with exactly two spanning trees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.