# Find a particular connected graph within a complete graph keeping all vertices

My problem is as follow, imagine a complete undirected graph with weighted edges, i would like to extract a connected graph keeping all the vertices and where the edge with the highest weight is the minimum one compared to all others possible configurations.

Is there another solution than bruteforce it.

• A minimum spanning tree minimize the sum of all edges and prevent cycles. I don't care about have cycles, i'm focused on the heaviest edge exclusively, not the sum of edges. Thank you – KyBe Nov 4 '17 at 16:24
• Can you give an example of when a minimum spanning tree is not a solution? – theyaoster Nov 4 '17 at 16:42
• @KyBe I know you don't require the connected subgraph to be a tree, but it wouldn't hurt you if it was. So the only question is whether an MST also has the property of minimizing the weight of the heaviest edge. And Ariel's answer seems to show that MSTs work. – David Richerby Nov 4 '17 at 22:34

To see why, suppose for the purpose of contradiction that $T$ is an MST which does not minmize the maximum weight. Let $(u,v)$ be the maximal weight edge in $T$, and $T'$ be a minimum bottleneck spanning tree. By our assumption $(u,v)\notin T'$, hence there exists a path from $u$ to $v$ in $T'$ which does not contain $(u,v)$, let us denote this path by $P$. Note that all the edges in $P$ are lighter than $(u,v)$. Remove $(u,v)$ from $T$, now $u,v$ are in different connected components. Suppose $P=(w_1=u,...,w_k=v)$, and denote by $i$ the minimal index such that $w_i$ and $w_{i+1}$ are in different connected components in $T\setminus\{(u,v)\}$. Now, $\left(T\setminus\{(u,v)\}\right)\cup\{(w_i,w_{i+1})\}$ is a spanning tree of $G$ with smaller weight, contradicting the fact that $T$ is an MST.