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$
1
  • $\begingroup$ I don't get how your argument works. $\endgroup$
    – Crostul
    Commented Apr 24, 2016 at 9:43

1 Answer 1

5
$\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$
2
  • $\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
    Commented Apr 24, 2016 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
    Commented Apr 24, 2016 at 9:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .