Let G = G(V,E) be an arbitrary, connected, undirected graph with vertex set V and edge set E.

Assume that each edge e 2 E has a distinct positive length `e, i.e., if e 6= e0 then `e 6= `e0. Define

the tediousness of any path P in G to be the length of the longest edge in P. Define the tediousness

between vertices u and v to be the tediousness of the least tedious path connecting u and v in G.

The Fun Subgraph Problem (FSP) is defined as finding S E such that:

(a) G(V,S) is connected.

(b) X

`e is as small as possible.

e2S

(c) For every pair of vertices u, v 2 V , the tediousness between u, v in G(V,S) is not greater than

the tediousness between u, v in G(V,E).

So, for example, taking S = E trivially achieves (c) and, since G is connected, also achieves (a). But,

most likely, it fails (b). Prove or disprove each of the following:

Proposition 1: If S is the set of edges in the MST of G, then condition (c) holds.

Proposition 2: If Proposition 1 is true, then the edges in the MST of G are a solution to FSP.

Proposition 3: Every optimal solution to the FSP must include every edge in the MST of G.

Note: You should try to prove each proposition independently of the other two.