Let $G$ be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of $G$ can have is _______.

A complete graph on 4 vertices ($K_4$) has $\binom{4}{2} = 6$ edges. A spanning tree on 4 vertices must contain exactly $4 - 1 = 3$ edges without forming any cycle.

To maximize the weight of the Minimum Spanning Tree (MST), we want Kruskal's algorithm to pick edges with weights as large as possible:

1. By Kruskal's algorithm, the two edges with smallest weights, $1$ and $2$, can never form a cycle because 2 edges cannot form a cycle. Thus, edges with weights 1 and 2 must always be included in the MST.

2. To avoid including the edge with weight $3$, the edge of weight $3$ must form a cycle with the edges of weights $1$ and $2$. This is possible if the edges with weights $1, 2,$ and $3$ form a triangle (cycle of length 3) on 3 vertices.

3. In that case, after selecting edges $1$ and $2$, edge $3$ is discarded because it forms a cycle with $1$ and $2$.

4. Next, the algorithm considers the edge with weight 4. Since the fourth vertex is not yet connected to the component of the other 3 vertices, an edge of weight 4 can connect the fourth vertex without forming a cycle.

5. Therefore, the MST edges chosen will have weights $1, 2,$ and $4$.

The total weight of this MST is:

It is not possible to achieve an MST weight larger than 7 because to avoid picking edge 4, edge 4 would also have to form a cycle with previously chosen edges, but the chosen edges $\{1, 2\}$ span only 3 vertices, so only one non-tree edge (the edge of weight 3) can form a cycle with them.

Hence, the maximum possible weight of an MST is 7.