[Solved] Consider a complete graph G with 4 vertices. The graph G has spanning trees.

Computer Science Engineering (CSE)
Design and Analysis of Algorithms
Consider a complete graph G with 4 verti...

Q.	Consider a complete graph G with 4 vertices. The graph G has spanning trees.
A.	15
B.	8
C.	16
D.	13
Answer» C. 16
Explanation: a graph can have many spanning trees. and a complete graph with n vertices has n(n-2) spanning trees. so, the complete graph with 4 vertices has 4(4-2) = 16 spanning trees.

View all MCQs in: Design and Analysis of Algorithms

Discussion

Related Questions

A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
How many spanning trees does a complete bipartite graph contain?
Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.
From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?
Which term defines all the complete bipartite graph that are trees?
Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?
Every graph has only one minimum spanning tree.
Which of the following is false in the case of a spanning tree of a graph G?