Last Updated: 21 Feb, 2021

# Total Number Of Spanning Trees In A Graph

Hard

## Problem statement

#### You’re given a connected undirected graph with N nodes and M edges. Your task is to find the total number of spanning trees of this graph.

##### Note :
``````A spanning tree T of an undirected graph G is a subgraph that is a tree that includes all of the vertices of G. A graph that is not connected will not contain a spanning tree.
``````
##### Input Format :
``````The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and M, the number of nodes, and the edges.
The next ‘M’ line of each test case contains two space-separated integers X and Y, denoting an edge between X and Y.
``````
##### Output Format :
``````For every test case, the only output line should contain an integer X, the total number of spanning trees in a graph.

The output of each test case should be printed in a new line.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10
N-1 <= M <= N*(N-1)/2
0  <= 'X', 'Y' <= N - 1

Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of nodes and edges, respectively. And, 'X', 'Y' denotes the node in the graph.
Time limit : 1 sec
``````

## Approaches

### 01 Approach

First, check if the given graph is a tree or a complete graph.

1. If the given graph is a tree, then the number of spanning-tree will be 1.
2. If the given graph is a complete graph, then the number of spanning trees will be equal to N^(N-2) (Cayley’s Theorem), where N is the number of nodes in the graph.