Question

Draw a graph that has more than one minimum spanning tree.

Short answer

A square-shaped graph with all edges equal weight offers more than one minimum spanning tree. These MSTs are: MST 1 (edges AB, BC, CD) and MST 2 (edges BC, CD, DA), both having a total weight of 3 units.

Step-by-step solution

Create the Base Shape

Choose an identifiable shape that has more than one route from one point to another. A square or rectangle serves as the best example here. Draw in a square shape with four vertices named, for instance, A, B, C, D, with AB, BC, CD and DA as edges. Ensure all edges have equal weights, e.g., all having a weight of 1.

Identify Possible Minimum Spanning Trees

A minimum spanning tree is a subgraph that spans all the vertices in a graph while having the minimal total edge weight possible. Advocating the equal edge weights in our square, there are 2 possible MSTs: MST 1 includes edges AB, BC, CD. MST 2 includes edges BC, CD, DA. Both MSTs cover all vertices (A, B, C, D) and have same total weight (3 units).

Depict Minimum Spanning Trees

For visual understanding, draw the two MSTs independently, showing the graph in a different color or style to differentiate the minimum spanning trees from the complete graph.