Minimum Spanning Tree Quiz Online Practice Test

1. Which statement about a spanning tree of a graph ( G ) is incorrect?

It is a tree that spans ( G )

It is a subgraph of ( G )

It includes every vertex of ( G )

It can be either cyclic or acyclic

2. Every graph has only one minimum spanning tree.

True

False

Sometimes true

Sometimes false

3. For a complete graph ( G ) with 4 vertices, how many spanning trees does ( G ) have?

4. Which approach is used to tackle the Travelling Salesman Problem?

Spanning tree

Minimum spanning tree

Bellman-Ford algorithm

Depth-First Search traversal

5. Given an undirected graph ( G ) with vertices {A, B, C, D, E} where each edge has a distinct weight, and edge CD has the minimum weight while edge AB has the maximum weight, which statement is incorrect?

Every minimum spanning tree of ( G ) must include edge CD

If edge AB is part of a minimum spanning tree, its removal would disconnect ( G )

No minimum spanning tree includes edge AB

( G ) has a unique minimum spanning tree

6. If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.

True

False

Sometimes true

Sometimes false

7. Which of the following is not a method for finding the minimum spanning tree of a graph?

Boruvka’s Algorithm

Prim’s Algorithm

Kruskal’s Algorithm

Bellman-Ford Algorithm

8. Which statement is incorrect?

Spanning trees do not contain any cycles

A minimum spanning tree has ( n - 1 ) edges if the graph has ( n ) vertices

An edge ( e ) that belongs to a cut in the graph and has a weight smaller than any other edge in the same cut will be present in all minimum spanning trees

Removing an edge from a spanning tree will not disconnect the graph

Test Name:	Minimum Spanning Tree Quiz
Subject Category:	Computer Science
Test Type:	Multiple Choice Questions
Total Score / Questions:	8 / 8
Time Allowed:	10 Min
Who Should Practice this Test:	Students, job seekers, or professionals preparing for competitive exams and interviews.

Minimum Spanning Tree MCQ Quiz Online Practice Test