37.9k views
0 votes
The minimum spanning tree of an undirected graph G exists if and only if G is connected. True or False?

User Kirubel
by
5.0k points

1 Answer

2 votes

Answer: True

Step-by-step explanation:

The definition of minimum spanning tree(MST) says that the graph must be connected and undirected to be considered for MST. It has (V-1) edges where V is the number of vertices. The minimum spanning tree is implemented using Kruskal's algorithm whereby it starts by considering the minimum weighted edge and covers all the edges upto (V-1) edges. So for MST it has to be connected

User A Little Sheep
by
5.2k points