The complete graph is connected, and the elementary operation preserves connectivity because it destroys cycles. The graphs obtained are therefore connected and have at least $n-1$ edges. It remains to see if we can obtain a tree.

The key observation is that a tree is bipartite, whereas $K_{n}$ (for $n \geqslant 3$, the only interesting case) is not! Let $G$ be a graph and $G^{\prime}$ a graph obtained by an elementary operation from $G$. Suppose $G^{\prime}$ is bipartite, say with $S\left(G^{\prime}\right)=S^{\prime} \cup S^{\prime \prime}$. The graph $G$ is obtained from $G^{\prime}$ by adding an edge to a path $v_{1} v_{2} v_{3}$ of length 3 to form a 4-cycle. Since $\mathrm{G}^{\prime}$ is bipartite, we must have $v_{1}$ and $v_{3}$ both in $S^{\prime}$ or in $S^{\prime \prime}$, and adding the edge $v_{3} v_{1}$ still gives a bipartite graph. Therefore, $G$ is bipartite. Therefore, we cannot obtain a tree from the complete graph, and the minimum number of edges is $\geqslant n$.

The bound $n$ is achievable. Let $G_{n}$ be the graph with $n$ edges formed by a path of length $n-2$ to which a triangle is added at one end. We show by induction on $n \geqslant 3$ that we can obtain $G_{n}$ from $K_{n}$. For $n=3$, it is clear. But from $K_{n}$ for $n \geqslant 4$, we can use elementary operations to remove all edges connecting a fixed vertex to the others except one, and apply the induction to the $\mathrm{K}_{n-1}$ on the others.
Let G be a complete graph with $n$ vertices. We perform a sequence of elementary operations consisting of choosing a 4-cycle (if one exists) and removing an edge. What is the smallest number of edges possible among the graphs we can reach?