Note that in the above graph, all edges have distinct weights. Hence the graph has a...

  

Transcribed Image Text:

Note that in the above graph, all edges have distinct weights. Hence the graph has a unique MST. To show that edge (B, D) is included in the MST, we only need to find a cut such that (B, D) is a light (cheapest) edge crossing the cut. For example, ({B}, V {B}); here V denotes the entire set of vertices. (a) (5 points) Show that (G, H) must be included in the MST. (b) (5 points) Show that (D,G) must be included in the MST. Activate Wir Go to Settings A 11 B 9 C 10 6 7 5 2 D E 14 3 12 1 15 LL F G H 13 4 Note that in the above graph, all edges have distinct weights. Hence the graph has a unique MST. To show that edge (B, D) is included in the MST, we only need to find a cut such that (B, D) is a light (cheapest) edge crossing the cut. For example, ({B}, V {B}); here V denotes the entire set of vertices. (a) (5 points) Show that (G, H) must be included in the MST. (b) (5 points) Show that (D,G) must be included in the MST. Activate Wir Go to Settings A 11 B 9 C 10 6 7 5 2 D E 14 3 12 1 15 LL F G H 13 4