Having solved the following exercise, I wonder what happens if you change it slightly.
Let $n \geq 4$. A bored mathematician plays the following game: She starts with a complete graph $K^n$. In each turn she selects a cycle graph $C^4$ contained in the current graph and deletes one of its edges. The game ends when there is no $C^4$ left. Her aim in the game is to have as many turns as possible. If she plays the game with optimal strategy, what is the smallest number of edges the last graph in the game has?
Let us now change the rules of the game: Let $n \geq k>4 $. Change the expression $C^4$ in the above exercise to $C^k$. If she plays the game with optimal strategy, what is the smallest number of edges the last graph can have?
My solution to the original exercise:
The last graph has $n$ edges. I proved it by showing that the last graph has to be connected and non-bipartite. Hence, it has at least $n$ edges. Then I gave a graph with precisely $n$ edges that can be obtained in the game (which I proved via induction). The graph I chose was a path of length $n-1$ in which the first and the third vertex are connected by an edge.
Returning to the modified exercise:
If k is even, then the last graph has to be connected and non-bipartite still. However, my previously chosen graph cannot be such a last graph.
If k is odd, then it is not even clear that the last graph cannot be bipartite.
Any thoughts?
The smallest possible number of edges at the end is:
First, I will show to get to $n$ edges for any $k$. To do this, first we reduce to the case $n=k$. Whenever $n>k$, we fix a vertex $v$ of the $n$-clique and remove all but one of its edges: as long as it has two edges $vw_1, vw_2$, find a $w_1,w_2$-path in the rest of the clique (which is untouched) of length $k-2$, use $vw_1$ and $vw_2$ to turn it into a $k$-cycle, and delete one of the edges incident to $v$. Once $v$ has degree $1$, we can ignore it; we'll never be able to delete that edge, so we can pretend that both $v$ and its only edge don't exist.
Once we have a $k$-clique, number the vertices $v_1, \dots, v_k$. We'll begin by deleting edges until left with the $2k$-edge graph $G$ that consists of:
(Unrelatedly, this graph is the reason I want to call the $k$-cycle $C_k$ rather than $C^k$, because this graph is the square of the $k$-cycle: it is $C_k^2$. Sorry, Diestel.)
To get to $G$, here is a cycle that will get rid of any other edge $v_i v_j$. (In the diagram below, $v_1, \dots, v_k$ are arranged around a circle.)
Note that aside from $v_iv_j$, no edges outside $G$ are used.
Next, whenever we have two adjacent $2$-step edges $v_i v_{i+2}$ and $v_{i+1} v_{i+3}$, we can delete one of them by using the cycle whose vertices, in order, are $$ v_1, v_2, \dots, v_i, v_{i+2}, v_{i+1}, v_{i+3}, v_{i+4}, \dots, v_k. $$ We can repeat this until we have only one of the $2$-step edges left. Now, delete one of the edges along the cycle with vertices $v_1, v_2, \dots, v_k$ in order, and we are left with a graph on $k$ edges.
Not only is this optimal when $k$ is even (because of your bipartite observation) but it's also optimal when $n=k$. In that case, if we could get to $k-1$ edges, we must have gotten there by deleting one edge from the $k$-cycle, but there's no graph with $k$ vertices and $k+1$ edges which can get to the $k$-cycle.
Now, to reduce to $n-1$ edges when $k$ is odd and $n \ge k+1$, we modify the approach above very slightly.
Instead of reducing to the $n=k$ case, we reduce to the $n=k+1$ case in exactly the same way. We call the vertices $v_0, v_1, \dots, v_k$ and forget about $v_0$ for now. We proceed as before until we have the graph $G$ described above - except we have $1$ more vertex ($v_0$) and $k$ more edges ($v_0 v_1, \dots, v_0 v_k$).
With this extra help, it is easy to delete all the $2$-step edges. (We assume $k > 3$, because for $k=3$ there are no $2$-step edges; $G$ is just a clique on $3$ vertices, and with $v_0$ it becomes a clique on $4$ vertices.) To find a cycle that lets us delete edge $v_i v_{i+2}$, start with the $(k-1)$-cycle visiting vertices $v_1, v_2, \dots, v_i, v_{i+2}, v_{i+3}, \dots, v_k$ in that order, and replace some edge $v_j v_{j+1}$ with a length-$2$ path going through $v_0$.
Now we are left with a wheel graph: a $k$-cycle on vertices $v_1, \dots, v_k$, together with all the edges out of $v_0$. Here is where we use the fact that $k$ is odd. Whenever both edges $v_0 v_i$ and $v_0 v_{i+2}$ are present for any $i$, we can delete one of them: use the $k$-cycle visiting vertices $v_1, v_2, \dots, v_i, v_0, v_{i+2}, \dots, v_k$ in that order. When $k$ is odd, the $k$ edges out of $v_0$ form a single sequence $$ v_0 v_1, v_0v_3, v_0v_5, \dots, v_0 v_k, v_0 v_2, v_0 v_4, \dots, v_0 v_{k-1} $$ in which each edge can help us delete the previous edge, using the strategy above. Going in that order, we can leave only one edge out of $v_0$.
Finally, deleting one edge of the remaining $k$-cycle leaves a tree, finishing the proof.