Background:
A graph is connected if there is a path between all pairs of vertices.
A graph has a cycle if there exists two vertices with an edge between them and a path between them that doesn’t use that edge.
A graph is a tree if it is connected and does not contain a cycle.
If you remove one edge from a cycle, it’s no longer a cycle.
Definition:
The heaviest edge of a cycle is the edge that corresponds to the largest vertex in the cycle and its largest neighbor. To compare two vertices, assume each vertex corresponds to a unique integer.
Question:
Given a connected graph, if we remove the heaviest edges of all cycles, is the result a spanning tree of that graph? Or can the resulting graph be disconnected?
Example:
Vertices: {0,1,2,3}
Edges: {01,02,03,13,23}
There are 3 cycles: 0130 0230 01320
The heavy edges (for each of the 3 cycles, respectively) are: 13 23 23.
Removing the heavy two edges results in the spanning tree with edges: {01 02 03}
Best Answer
It's always a spanning tree.
You probably already noticed this, but for completeness: the resulting graph is acyclic, because every cycle in the original graph has been destroyed. So we need to show that the result is still connected.
Another characterization of connectivity will be useful here: a graph $(V,E)$ is connected if and only if for every nonempty $S \subsetneq V$, there is a crossing edge: an edge between a vertex in $S$ and a vertex in its complement $V \setminus S$. So let's check this for the graph after deletions.
For a given set $S$, because our starting graph was connected, there are some crossing edges. Let $e$ be the lightest of these edges. I claim that the edge $e$ is never deleted, and so there is also a crossing edge in the graph we get at the end.
For $e$ to be deleted, we'd first have to find a cycle containing it. That cycle contains at least one vertex in $S$ and at least one vertex not in $S$. Following that cycle starting from $S$, at some point we leave $S$ - but then we have to come back to $S$ by a different edge. This can happen multiple times, but even if it only happens once, we see that the cycle contains at least two crossing edges: $e$, and some other edge $e'$ (and maybe others).
Since $e$ is the lightest crossing edge, it is in particular lighter than $e'$. So it is not the heaviest edge on this cycle, and will not be deleted when we consider this cycle. The same argument holds for every cycle containing $e$, so the edge $e$ will never be deleted.
In fact, the tree $T$ we get at the end is a minimum spanning tree.
To see this, take any other spanning tree $T'$. Let $e$ be an edge of $T$ not in $T'$. Adding $e$ to $T'$ creates a cycle, and deleting any edge of that cycle would create another spanning tree. Let's add $e$ and delete the heaviest edge of that cycle.
That heaviest edge is definitely not $e$, because $e$ is not the heaviest edge of any cycle. So we added $e$ to $T'$, then deleted an edge heavier than $e$. This means that we've reduced the total weight of $T'$: therefore, $T'$ is not a minimum spanning tree. Since some minimum spanning tree must exist, it can only be $T$.