Question

Find a connected weighted simple graph with the fewestedges possible that has more than one minimum spanning tree.

Short answer

The connected weighted graph is

Step-by-step solution

Definition

A graph is connected if there exists a path between every pair of vertices.

Weight of the edge

The easiest weighted simple graph with more than one spanning tree, are weighted simple graphs with the same weight on each edge and with more than \({\bf{n - 1}}\) edges (when there are \({\bf{n}}\) edges).

For example, let us take a graph \({\bf{G}}\) with \(4\) vertices \({\bf{a, b, c, d}}\) and an edge with weight \(1\) between every pair of vertices.

Obtaining the graph

Then any subgraph of \({\bf{G}}\) that is a tree, will also be a minimal spanning tree. Two possible minimal spanning trees are given in the image below (note that the total weight is \(3\) in both minimal spanning trees).

Note: The two given minimal spanning trees are not even isomorphic in this case.