show that in an nvertex graph a set of n1 edges that form no

show that in an n-vertex graph, a set of n-1 edges that form no circuits is a spanning tree.

Solution

We know that \" A tree is a spanning tree of a graph G is a subgraph of G that contains all of the vertices of G\".

Since tree is connected, there must be at least n-1 edges to connect n vertices. Suppose that there are more than n-1 edges then either the root has in degree 1 or some other vertex has in degree at least 2, which is impossible. Thus there there are exactly n-1 edges.

Since T is connected there exists a simple path between every vertex. So it has no circuits.

Hence in an n vertex graph , a set of n-1 edges that form no circuits is a spanning tree.