Question 2.26

26. Assume that every edge of a graph G has a different cost. If Kruskal’s algorithm is used to find the minimum-cost spanning tree T for graph G, which of the following statements must be true?

  1. Any other spanning tree for graph G will have more edges than T.
  2. Any other spanning tree for graph G will have a greater cost than T.
  3. The edge of graph G having greatest weight is included in T.

26.

b