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?
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.