MINIMUM SPANNING TREE

1. In an undirected graph, the shortest path between two nodes lies on some minimum spanning
tree.
A: False.

2. If the edges in a graph have different weights, then the minimum spanning tree is unique.
A: True.

3. If the edge with maximum weight belongs to a cycle, then there exists some MST that
does not contain this edge.
A: True

4. Adding a constant to every edge weight does not change the minimum spanning tree.
A: True

5. There can be more than one minimum spanning trees if the weight of the edges are all distinct
A.False

6. If all weights are the same, every spanning tree is minimum.
A. True

7. Greedy algorithm runs in exponential time
A. False

8. A minimum spanning tree should contain all edges of the graph
A. False

9. A minimum spanning tree should contain all vertices of the graph
A.True

10.Adding an edge to a spanning tree of a graph G always creates a cycle.
A.False

11. Adding an edge to a spanning tree connecting two existing vertices of a graph G always creates a cycle.
A. True

12. For any cycle in a graph, the cheapest edge in the cycle is in a minimum spanning tree.
A. False