Question 2.101

71. Determine whether each of the following statement: is true or false for a minimum-cost spanning tree T for a weighted connected graph G:

  1. T contains a cheapest edge in the graph.
  2. T cannot contain a most expensive edge in the graph.
  3. T contains one fewer edge than there are vertices in G.
  4. There is some vertex in T to which all others are joined by edges.
  5. There is some vertex in T that has valence 3.

71.

(a) True

(b) False (unless all the edges of the graph have the same weight)

(c) True

(d) False

(e) False