recategorized by
369 views
0 votes
0 votes
How we get maximum no. of spanning tree for give $n$ node is $n^{(n-2)}$
recategorized by

1 Answer

0 votes
0 votes
this formula is applicable when graph is complete connected graph means every nodes to connected to other nodes

n= number of nodes say 5

total number of spanning tree =n^(n-2) =5^3 =125 spanning trees.

if graph is not complete connected graph ,in that case use kirchaff theorem.(represent graph in adjacency matrix).

Related questions

1 votes
1 votes
1 answer
2
akash.dinkar12 asked Apr 8, 2019
846 views
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
32 votes
32 votes
14 answers
3
Arjun asked Feb 7, 2019
20,974 views
Let $G$ be an undirected complete graph on $n$ vertices, where $n 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to$n!$$(n-1)!$$1$$\frac{(n-1)!}{2}...