A connected graph G has 4 vertices and 4 edges of costs 1,2,3 and respectively 4....

  

Transcribed Image Text:

A connected graph G has 4 vertices and 4 edges of costs 1,2,3 and respectively 4. (a) Show that G is not a tree. (b) Show that G has a single minimum spanning tree. (Hint: For example, think how Prim's algorithm constructs the minimum spanning tree). I (c) Draw a connected graph G with 4 nodes and 4 edges of costs 1,2,3,4, respectively, so that the minimum spanning tree contains the edge of cost 4. The 4 nodes are below, you need to draw the 4 edges and indicate their cost. a A connected graph G has 4 vertices and 4 edges of costs 1,2,3 and respectively 4. (a) Show that G is not a tree. (b) Show that G has a single minimum spanning tree. (Hint: For example, think how Prim's algorithm constructs the minimum spanning tree). I (c) Draw a connected graph G with 4 nodes and 4 edges of costs 1,2,3,4, respectively, so that the minimum spanning tree contains the edge of cost 4. The 4 nodes are below, you need to draw the 4 edges and indicate their cost. a