0
$\begingroup$

Prove that any two spanning trees for a graph has the same number of edges.

Proving by contradiction. Assume that there exists two spanning trees with different number of edges.

Take $G$ to be the original graph with $n$ number of edges. A spanning tree/ subgraph $H$ is obtained from $G$ by removing one edge from $G$ thus giving $n-1$ edges

while another spanning tree/ subgraph $B$ is obtained from $G$ by removing two edges from $G$ thus giving $n-2$ edges.

And since $H$ is a spanning tree with $n-1$ edges $H$ cannot have any circuit. And thus $n-1$ is the minimmum number of edges to form a tree.(Ie removing any more edges will not give a connected graph) Thus we know that graph $B$ with $n-2$ edges cannot form a tree, thus a contradiction. Im getting the idea but could anyone improve on my proof and explain whether is it correct. Thanks

$\endgroup$
  • $\begingroup$ I don't get how your argument works. $\endgroup$ – Crostul Apr 24 '16 at 9:43
4
$\begingroup$

The proof is actually very simple, knowing these two facts:

  1. If a tree has $|V|$ vertices, then it has $|V|-1$ edges. This is proved easily by induction.

  2. If $G$ is a connected graph with $|V|$ vertices, and $T$ is a spanning tree of $G$, then the set of vertices of $T$ coincides with the set of vertices of $G$ (this is the definition of spanning tree). In particular, $T$ has $|V|$ vertices.

From these two facts, you have that any spanning tree must have exactly $|V|-1$ edges.

$\endgroup$
  • $\begingroup$ Yup my main idea is that ,Assuming that there exists two spanning trees with different number of edges. and that one of them have $V-1$ edges then the other cannot have $V-1$ edges thus a contradiction. $\endgroup$ – ys wong Apr 24 '16 at 9:50
  • 1
    $\begingroup$ Well, you don't need contradiction here. Any two spanning trees have $|V|-1$ edges, hence they have the same number of edges (which is $|V|-1$). $\endgroup$ – Crostul Apr 24 '16 at 9:51

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.