Question

Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?

(a) Graph M has no minimum spanning tree

(b) Graph M has a unique minimum spanning trees of cost 2

(c) Graph M has 3 distinct minimum spanning trees, each of cost 2

(d) Graph M has 3 spanning trees of different costs

The question was asked in an interview for internship.

My question comes from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

The correct option is (c) Graph M has 3 distinct minimum spanning trees, each of cost 2

The best explanation: Here all non-diagonal elements in the adjacency matrix are 1. So, every vertex is connected every other vertex of the graph. And, so graph M has 3 distinct minimum spanning trees.