Question-53

Data Structure
Graph

Consider an undirected connected graph \(G\) with \(V\) vertices, where all edge costs are distinct. Which of the following statement(s) is/are true?

  1. Let \(V\) be partitioned into two non-empty sets \(X\) and \(Y\). Let \(e = (s, t)\) be the minimum cost edge, with \(s\) belonging to \(X\) and \(t\) belonging to \(Y\). Then edge \(e\) must definitely belong to the minimum cost spanning tree of \(G\).
  2. Let \(C\) be any cycle in \(G\), and let edge \(e = (u, v)\) be the most expensive edge belonging to \(C\). Then edge \(e\) does not belong to the minimum spanning tree of \(G\).