296 views
0 votes
0 votes
What is the number of spanning tree in cyclic graph

1 Answer

1 votes
1 votes

Spanning tree is a graph that does not contain a cycle.

$\Rightarrow$ we can transform a cyclic graph into spanning tree by removing any one edge from it.

a Cyclic graph has edges =vertices= n(say).

$\Rightarrow$ we could remove any one edge  from n edges to get a spanning tree

$\Rightarrow$ this could be done in n ways.

Hence the number of spanning tree in the cyclic graph is equal to the number vertices that cyclic graph.

edited by

Related questions

0 votes
0 votes
1 answer
1
amit166 asked Jan 27, 2019
186 views
formule for1.number of binary tree2.number of binary search tree3.number labeled binary tree4.number of unlabeled binary tree
3 votes
3 votes
1 answer
2
Abhijeet_Kumar asked Oct 17, 2017
242 views