0
$\begingroup$

Let $\tau (G)$ be the number of spanning trees in graph $G$.

I will prove the following claims:

(1) if T is a tree, $\tau (T)=1$

(2) if G is derived from a tree T by replacing one edge of T by a multiple edge of multiplicity k, then $\tau (G)=k$

(3) $\tau (C_n)=n$

(1)Suppose a tree has two spanning trees. Consider two vertices x, y in T. Since there are two spanning trees, there are two distinct walks between x and y: $(x,p_1,...,p_n,y)$ and $(x,q_1,...,q_m,y)$. Then $(x,p_1,...,p_n,y,q_m,...,q_1,x)$ is a cycle in T. This is a contradiction because a tree by definition is a graph which contains no cycles.

(2) Let the edge $ab$ be in a tree be replaced by k edges. Since $ab$ is a bridge, so are the multiplied k edges. Hence, the graph obtained by choosing one of the k edges and deleting the k-1 edges is a tree. There are k such possible trees, and $\tau (T)=1$ so $\tau (G)=k$.

(3)$C_n$ has $n$ edges. Therefore, deleting one edge will result in a graph of $n$ vertices and $n-1$ edges, and this graph is a tree. There are n possible such tree, and $\tau (T)=1$ so $\tau (G)=n$.

$\endgroup$
  • $\begingroup$ Where did you use (2)? $\endgroup$ – Chris Godsil Jun 6 '13 at 14:06
1
$\begingroup$

(1) Is wrong. This claim "Since there are two spanning trees, there are two distinct walks between x and y" is incorrect, as you already chose $x,y$.

Note that the two spanning tree might have a lot of overlap.

Also " Then $(x,p_1,...,p_n,y,q_m,...,q_1,x)$ is a cycle in $T$" is not correct either but this one can be fixed easily. This is a closed walk, but necessarily a cycle. Anyhow, any closed walk contains a cycle.

You need to fix the first inexactity though.

A better idea is the following: Consider a spanning tree $T'$ of $T$. How many vertices and edges does $T'$ have? What about $T$? What does this mean?

(2) Note that the multiple bridges are not bridges, erasing one will leave the new graph connected. Anyhow, any edges excepting the multiedge is still a bridge and thus must be in any spanning tree.

Besides those, you need one more edge from the multiedges by the tree formula.

(3) Is almost perfect.

The only thing needing fixing is this:

" deleting one edge will result in a graph of $n$ vertices and $n-1$ edges, and this graph is a tree."

Not any graph with $n$ vertices and $n-1$ edges is a tree. But if you remove an edge from a cycle, the resulting graph is connected, and any connected graph with $n$ vertices and $n-1$ edges is a tree.

Or alternately, you can say that removing an edge will create a graph without cycles, and any graph without cycles and $n$ vertices and $n-1$ edges is a tree.

$\endgroup$
  • $\begingroup$ (1)A spanning tree in $T'$ has v vertices and v-1 edges. Since $T$ also has v vertices and v-1 edges, the two must be the same graph. (My reasoning for this is that the set of edges/vertices in $T'$ must be a subset of the set of edges/vertices in $T$. Hence, if the orders of both sets are the same, they must be the same set; is this correct?) (2)>Besides those, you need one more edge from the multiedges by the tree formula. Can you explain this part? By "tree formula", do you mean the fact that a tree of v vertices must have v-1 edges? $\endgroup$ – user81055 Jun 6 '13 at 20:22
  • $\begingroup$ @user81055: (1) Yes. (2) Yes, that’s what N. S. means by tree formula. The point is that you need the $v-2$ bridges, and you need one more edge to bring the total to $v-1$; it must be one of the multi-edges. $\endgroup$ – Brian M. Scott Jun 6 '13 at 22:52

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.