Algorithms - Algorithm Design Techniques

Graph G has no minimum spanning tree (MST)

Graph G has a unique MST of cost n-1

Graph G has multiple distinct MST's, each of cost n-1

Graph G has multiple spanning trees of different costs

There exists a cutset in G having all edges of maximum weight.

There exists a cycle in G having all edges of maximum weight.

Edge e cannot be contained in a cycle.

All edges in G have the same weight.

There is a minimum spanning tree containing e

If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.

Every minimum spanning tree has an edge of weight w;

e is present in every minimum spanning tree

(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)

(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)

(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)

(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)