You don't really need induction for this. Let $u$ and $v$ be adjacent vertices, and let $U$ and $V$ be the sets of $n/2$ other vertices adjacent to $u$ and $v$ respectively. Since $|U|+|V|+|\{u,v\}|=n+2$ is greater than $n$, we must have $U\cap V\not=\emptyset$. So in fact we've proved more, namely that if each vertex in a graph on $n$ vertices (with $n$ even) has degree $n/2+1$, then every pair of adjacent vertices is part of a triangle.
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$.
Best Answer
$k=4$ is a bit too small to visualize, so here is a picture for $k=8$:
Imagine that we are looking at a permutation $\sigma$ that permutes these $8$ vertices in a cycle, and we want a graph fixed by this permutation. (Maybe there are also other vertices we're not looking at, because we don't care what they do for the moment.) Then:
Essentially, if you rotate the picture above by $45^\circ$, then each edge is moved to another edge of the same color.
In general, there are $\lfloor \frac k2\rfloor$ orbits characterized by the length of an edge, when we draw the vertices in the cycle as a regular $k$-gon.