For context, the following is the original wording found in the first post of this thread. ~dj In a country there are $n>3$ cities. We can add a street between $2$ cities $A$ and $B$, iff there exist $2$ cities $X$ and $Y$ different from $A$ and $B$ such that there is no street between $A$ and $X$, $X$ and $Y$, and $Y$ and $B$. Find the biggest number of streets one can construct! I'll restate it, so that it's exactly like in ISL 2004 . We are given a complete graph on $n$ vertices, and the only allowed operation is to find a $4$-cycle, pick one of its edges, and delete it. The question is: what is the minimal number of edges we're left with? (the answer to the problem from the TST is then obtained from that one by subtracting it from $\frac{n(n-1)}2$) I think the answer (to the reworded question) is $n$: I'm sure constructing n example with $n$ edges is not a problem, so I'll focus on proving that it's the minimal value. First of all (even though we could skip this part and go straight to showing that the minimal number is $n$), it's obvious that an operation does not disconnect the graph, so the minimal number of edges left is $\ge n-1$. What we have to show is that it cannot be $n-1$, i.e. that we can't be left with a tree in the end. Assuming that in the end we're left with a tree, there must be a moment when we destroy the last odd cycle. This can only be done if the edge we remove in the respective operation belongs to the cycle. A quick look through all the cases should show that getting rid of all the odd cycles like this is impossible (the cases being: the odd cycle our edge is on and the $4$-cycle necessary for the operation share precisely one edge, the one we remove, or $2$ edges, or $3$, and, when they share $2$ edges, the two edges could be adjacent or opposite in the $4$-cycle, so there are $4$ cases in total, all of them easy to check). Is it Ok?

Or also noting tha if we end up with a tree it is bypartite, and recovering our graph would keep it bypartite Implying that ourm initial complete graph was bypartite too, contradiction!

nice. another interesting problem would be to determine exactly which graphs can be reached from a complete graph in this way. we know that bipartite graphs can't be reached, but i have the following question: can all non-biparitite connected spanning subgraphs be reached?

Can anyone tell me if this is correct? Claim: Every non-bipartite connected graph can be reached from a complete graph by the operation of deleting an edge of a 4-cycle. Proof: Suppose that there exists a non-bipartite and connected graph such that no edge addition creates a 4-cycle, call it $G$. First lets prove $G$ contains a $K_3$. Since $G$ is not bipartite consider the smallest odd cycle, say $v_1,...,v_{2k+1}$. If $k=1$ we are done so assume $k>1$. Then the edge $v_1 v_4$ does not exists since it would create a smaller odd cycle, so we can add an edge between these vertices but adding it would createa 4-cycle. Contradiction, so $k=1$, and we have the disired $K_3$. Now lets prove $G$ can not contain a $K_3$. Suppose $G$ contains a $K_3$ say $T$. Let $K$ be the largest complete graph containing $T$, (maybe $T=K$). $G$ can't be $K$ because we would not be able to perform the opperation of adding an edge. So there exist a vertex $x$ that is adjacent to some vertices of $K$ (since the graph is connected) but not to all (since $K$ is the largest complete graph containing $T$). Since $x$ has at least one neighbor in the complete graph $K$, adding any edge from $x$ to another vertex of $K$ creates a 4-cycle. Contradicton, so $G$ must contain a $K_3$

It looks correct.

I'll go with the official wording.

Is not hard! I explain official wording I prove there is always some odd cycle. At beginning is obvious. Now at any point, take smallest odd cycle $A_1A_2 \ldots A_m$ with odd $m$. Notice that no edges $A_kA_{\ell}$ exist if $k, \ell$ not consecutive. If cycle is destroyed, then assume we deleted $ A_1A_2$. If the 4cycle we took was $A_1A_2XY$ with $X,Y \neq A_i$ then new odd cycle exists! $A_3 \ldots A_m XY$. If the 4cycle we took was $ A_1A_2A_3X$, is easy to see $ X \neq A_i$ so a new odd cycle exists! By replacing $A_2$ with $X$. And is obvious the 4cycle cannot be $A_1A_2A_iA_j$ because this means $i=3, j=m$ but $3,m$ are not consecutive in my cycle. So there is always odd cycle! Also notice that graph is always connected, since if we used edge $XY$ from 4cycle $XYZW$, then we can use $XWZY$ instead. So graph is connected and has a cycle so it has at least $n$ edges! Construction is inductive and very easy. The answer is $\boxed{n}$!

I attempted this problem about an year ago and solved it, but at that time I didn't post a solution. So I'l do that now. Experimenting with small value suggests that the answer is $n.$ Lemma 1. The answer is no less than $n.$ Proof. Of course, note that no vertex can become independent by such operations, and we cannot destroy the existence of a cycle so at any point in time we have at least $n$ edges. Lemma 2. This $n$ is indeed achievable. Proof. For $n=4$ we can easily show this: if the graph is $abcd$ then delete $\overline{ab},\overline{ac}.$ Now we use induction. Let this result be true for some $n.$ We shall prove it for $n+1.$ Let the vertices be $A_1,..,A_{n+1}.$ First delete the edges $A_{n+1}A_1,A_{n+1}A_2,...,A_{n-1}A_n.$ Now $A_{n+1}$ has only one neighbor so we can effectively ignore it. By the induction hypothesis we can delete edges so that finally $n$ edges other than $A_{n+1}A_n$ are present. Hence we finally have $n+1$ edges as claimed. By induction the lemma has been proved. By the above lemmas, the answer is $n$ edges.

AdithyaBhaskar wrote: ... Lemma 1. The answer is no less than $n.$ Proof. Of course, note that no vertex can become independent by such operations, so at any point in time we have at least $n$ edges, the number of edges in a tree... The number of edges in a tree with $n$ vertices is $n-1$.

dgrozev wrote: AdithyaBhaskar wrote: ... Lemma 1. The answer is no less than $n.$ Proof. Of course, note that no vertex can become independent by such operations, so at any point in time we have at least $n$ edges, the number of edges in a tree... The number of edges in a tree with $n$ vertices is $n-1$. Oh sorry seems I wrote stuff half-mindedly. Will edit soon.

Particle wrote:

That was almost exactly my proof

First of all, we see that after each step, the graph remains connected. Therefore connectedness of the graph is an invariant. Thus, #min. edges $\ge n-1$. For #min. edges = n-1, we get a spanning tree. We show that one cannot obtain a spanning at the end. To show this, we assume to the contrary that it's possible to get a spanning tree at the end. Thus, it must be possible to "reconstruct" $K_n$. Before arriving at the contradiction, we give definitions. For any vertex $A$, consider its adjacent vertex $P$. Now, consider $P$'s adjacent vertex's adjacent vertex (say $Q$) Call the above operation $T$ We call a vertex $L$ an 'alternative vertex' of $A$ if $L$ is obtained after applying $T$ on $A$ finitely many times. Define $S:=\{P\mid P~~\text{is an alternative vertex of } A\}\cup\{A\}$ as the 'alternative set containing A' If $G$ is the spanning tree obtained at the end, then let $G=(V,E)$. Define $S':=E/S$ Clearly $S,S'$ are disjoint. During reconstruction, we connect $A$ to any $P\in S$. Continuing this, we see that this $A$ is connected to every element of $S$ only. But, $A$ cannot be connected to any vertex in $S'$. Thus, it is impossible to reconstruct $K_n$ and so it's not possible get a spanning tree at the end. Now we show that #min. edges = $n$ is possible. We first note that if $A$ was connected to any element in $S'$, it would be connected to all vertices in $S'$ due to our reconstruction (proof by induction). Thus, if we had $n$ edges left at the end, we could use a "free edge" to join $A$ to an element in $S'$, and thus $A$ would be connected to all the other vertices and we are done. $\blacksquare$ (Small note: While defining $S$, we must not consider any "loops" i.e. selection of elements of $S$ must be done by applying $T$ in a fixed "direction") Interestingly, the above reconstruction gives a possible generalization: Replace 4-cycle by a t-cycle (t>4), and let $n\ge t$ then #min edges at end =$n+t-4$

Nice problem! Here's my solution: The crux of the problem is the following claim:- CLAIM After each operation, the graph remains connected, and always has an odd cycle. Proof of Claim First we prove connectivity. FTSOC suppose after some operation the graph becomes disconnected. Then, before this move, the graph must be present in the form of two partitions $G_1$ and $G_2$, with exactly one edge $\{uv\}$ between these parts, where $u \in G_1$ and $v \in G_2$. But, in order to delete the edge $\{uv\}$, it must be part of a $4$-cycle. Since this $4$-cycle must return to $G_1$, so it requires atleast two edges between $G_1$ and $G_2$, a contradiction! So our graph remains connected. For the second part, consider the operation when an edge from a $(2k+1)$-cycle $C_1$ is deleted. This edge must also be a part of some $4$-cycle $C_2$. But then $C_1 \cup (C_2-C_1)$ is another odd cycle. So the graph always has atleast one odd cycle. Return to the problem at hand. Our claim directly gives that the final graph must have at least $n$ vertices. Now, we show that $n$ is always achievable. Call a graph $G$ on $n$ vertices good if it is of the following form- It consists of a triangle with vertices $a,b,c$. $\text{ }$ The remaining $\left \lfloor \frac{n-3}{2} \right \rfloor$ vertices, namely $u_1,u_2, \dots,u_{\left \lfloor \frac{n-3}{2} \right \rfloor}$ are joined to $a$. $\text{ }$ The remaining $\left \lceil \frac{n-3}{2} \right \rceil$ vertices, namely $v_1,v_2, \dots,v_{\left \lceil \frac{n-3}{2} \right \rceil}$ are joined to $b$. It's easy to see that such a graph has $n$ edges. We will show that, starting from $K_n$, we can always reach a good graph after finitely many operations. We proceed by induction on $n \geq 4$, with the result being easily seen to be true when $n=4$. Now suppose the result is true for some $n$. Consider $K_{n+1}$, and apply the inductive hypothesis to get to a graph consisting of a good graph $G$ on $n$ vertices, with all of the $n$ vertices joined to another vertex $w$. Then, we can delete $\{wu_i\}$ for all $1 \leq i \leq \left \lfloor \frac{n-3}{2} \right \rfloor$, since it is a part of the cycle $\{w,u_i,a,b\}$. By a similar argument, we can delete vertices of the form $\{wv_j\}$ for $1 \leq j \leq \left \lceil \frac{n-3}{2} \right \rceil$. Finally, delete $\{wb\}$ and $\{wc\}$, which we can do, as $wacb$ forms a $K_4$. Thus, we are left with $$(n+n)-\left(\left \lfloor \frac{n-3}{2} \right \rfloor+\left \lceil \frac{n-3}{2} \right \rceil+2 \right)=n+1$$edges. Then it's easy to see that this is also a good graph on $n+1$ vertices, completing the inductive step. $\blacksquare$

Solution from Twitch Solves ISL: The answer is $n$. As the case $n=4$ is easily done by hand, we will assume $n \ge 5$. To show that at least $n$ edges always remain, note that The operation preserves connectedness of the graph; The operation preserves the fact that the graph is not bipartite. This implies the graph will always have $n$ edges leftover (since a connected graph always has at least $n-1$ edges, but with equality only when it is a tree, and trees are necessarily bipartite). Conversely, for any $n \ge 5$ one can reach the graph consisting of a $K_5$ plus a path of length $n-5$ hanging off one vertex. Then one can prune the $K_5$ down to $C_5$ to achieve the desired construction. [asy][asy] draw(dir(0)--dir(72)--dir(144)--dir(216)--dir(288)--cycle, red); draw(dir(0)--dir(144)--dir(288)--dir(72)--dir(216)--cycle, lightblue); draw(dir(0)--2*dir(0), red); draw(2*dir(0)--3*dir(0), red); draw(3*dir(0)--4*dir(0), red); dotfactor *= 1.5; pen vtxpen = grey; dot(dir(0), vtxpen); dot(dir(72), vtxpen); dot(dir(144), vtxpen); dot(dir(216), vtxpen); dot(dir(288), vtxpen); dot(2*dir(0), vtxpen); dot(3*dir(0), vtxpen); dot(4*dir(0), vtxpen); [/asy][/asy]

@v_Enhance can you kindly provide the link of the twitch stream ? thank you in advance

oty wrote: @v_Enhance can you kindly provide the link of the twitch stream ? thank you in advance The Twitch stream is twitch.tv/vEnhance. You can find links to past broadcasts and schedule at https://web.evanchen.cc/videos.html.

The answer is $n$. We first prove the bound, then provide a construction. Let $G_n$ be the final graph. Claim: $G_n$ is connected. Proof: Suppose the graph disconnected at some point. The step just before that, there must have been two sets of vertices that were disjoint save for one edge. But it is impossible to delete this edge, since it cannot be a member of any cycle, contradiction. (Alternatively, simply note that the operation doesn't change the contentedness of the graph.) $\blacksquare$ Claim: $G_n$ is not a tree. Proof: Since we know $G_n$ is connected, it suffices to show that there is always an odd cycle. Simply note that the operation does not decrease the number of odd cycles; if an edge existed which was deleted and was part of an odd cycle, that odd cycle is now just a new odd cycle that is larger by 2 edges. $\blacksquare$ The second claim proves that $|G_n| \not = n-1$, and since the graph is connected, we must have $|G_n|\ge n$, proving the bound. Now we construct. For $n=4$, it is easy to see. The construction is inductive. Suppose we have constructed it for $n$, call the graph $G_n$. Start with $K_n$, and add a universal vertex $u$. Select two vertices $v_1,v_2$ in the $K_n$ which have some common neighbor $v_3$. Now, for any vertex $X\not = v_1,v_2$ in the $K_n$, consider the 4-cycle $uXv_1v_2$. Then delete edge $uX$. Repeat for all such $X$. So we only have $uv_1,uv_2$ coming out of $u$. Now, use the cycle $uv_1v_2v_3$ to delete $uv_2$. This leaves only the edge $uv_1$ from $u$. By induction we can end with $G_n$ having $n$ edges (WLOG it contains $v_1$). Hence we have added one edge, so we have made a valid $G_{n+1}$, completing the induction.

We claim the answer is $n$ and we proceed by induction. The proof for our base case $n=4$ can be done by hand. Now we induct. The crucial observation is that each vertex must have at least one edge passing through it, and that if a vertex has degree one it can be ignored, and this is true since a vertex with degree one cannot be part of a cycle. Now consider $K_n,$ and note that if we are to only focus on $n$ of the $n+1$ points and delete as many edges as possible that it must have at least $n$ edges. But note that the last vertex cannot have degree $0$, so the number of edges is at least $n+1.$ Now we construct in an inductive manner as well. We have already proved this works for $n=4$ before. Note that $K_{n+1}$ is isomorphic to a regular $n+1$ gon-with all of its diagonals drawn, and call the points $P,P_1,P_2,\ldots,P_{n}.$ Now delete the edges from $P_3$ to $P_{n-1},$ noting that this is always legal as the cycle $PP_1P_2P_k$ exists for $3\leq k\leq n-1.$ Now erase $P_2$ as the cycle $PP_2P_3P_n$ exists, and now erase $P_n$ as the cycle $PP_1P_2P_n$ exists. Now we ignore $P$ and note that the $K_n$ graph $P_1P_2\ldots P_n$ has a construction of $n,$ so the total is $n+1$ as desired.

We claim the answer is $n$, which we will prove by induction. The base case of $n = 4$ is obvious. Now, focus in on a vertex $v$. It's obvious that at the end, its degree will be at least $1$. By inductive hypothesis the other $n$ vertices have at least $n$ edges left, thus the best we can do is $n + 1$. To construct, isolate vertex $v$ and then vertices $v_1, v_2, \cdots, v_n$. First consider cycle $vv_1v_2v_3v$; delete edge $vv_1$. Then, consider cycle $vv_2v_3v_4v$, and go down the line. Our final one is $vv_{n - 2}v_{n - 1}v_nv$; here, after deleting $vv_{n - 2}$, we can consider $vv_{n - 1}v_{n - 2}v_nv$ in order to kill the $vv_{n - 1}$ edge. Thus we are done.

The answer is $\boxed{n}.$ $\emph{Construction: }$ Let $v$ be a vertex of the graph $G$ at some point in time. Suppose that 1) $G-v$ is complete and 2) there exist two edges adjacent to $v$. Then, it is easy to see that we may remove one of the edges adjacent to $v.$ Starting with the complete graph and applying the above result repeatedly, we can remove all but one of the edges adjacent to any given vertex. Now we can obtain $n-1+1=n$ edges by induction. $\emph{Proof: }$ Let $G'$ be the graph remaining when no further operations can be performed. Note that the operation preserves connectedness, so $G'$ is connected. Moreover, note that the operation preserves the property "has a cycle with length not equal to $4$, so $G'$ is not a tree. These conditions are enough to imply that $G'$ has at least $n$ edges.

My answer is $n$. The key idea is to find the example, by induction we can get a path $v_1v_2\dots v_n$ such that $v_iv_{i+1}$ it's an edge and also $v_1v_3$ with this configuration we have $n$ edges. The inductive step is first separate $K_{n+1}$ in $K_{n+1} - v_{n+1}$ this is a complete graph and with the induction we get the path and the extra edge, but also $v_{n+1}v_i$ is an edge. We take in descending order the cycles $v_{n+1}v_iv_{i-1}v_{i-2}$ and eliminate $v_{n+1}v_i$ with $i= n,n-1,\dots,4$. With this algorithm we eliminate almost every edge, then we take the cycle $v_1v_3v_2v_{n+1}$ and eliminate $v_1v_3$ after this we take the cycle $v_1v_2v_3v_{n+1}$ and we eliminate $v_2v_{n+1}$ this completes the induction. To prove that this is the minimum, we can check that always the operation preserves connectedness of the graph and always exists an odd cycle this can be checked manually, so the graph it's connected but is not a tree this implies that the number of edges is at least $n$.

We claim the answer is $n$. We will consider the reverse of the operation: we are looking for graphs $G$ that can be transformed into $K_n$ by adding edges one at a time, each of which creates at least one new $4$-cycle. For the construction, arbitrarily number the vertices $v_1, v_2, \dots, v_n$. Connect $v_1$ to all $n-1$ other vertices, and then connect $v_2$ to $v_3$. This graph has $n$ edges, and we claim it is possible to to reach $K_n$ using the reverse operation. Indeed, we can first add in $v_3v_4, v_4v_5, \dots , v_nv_2$ in that order. Then we can add in any edge $v_iv_j$ to create the $4$-cycle $v_1v_iv_jv_{j+1}v_1$ (where we define $v_{n+1} = v_2$). For the bound, clearly $G$ must be connected, so it remains to show $G$ cannot be a tree. We claim bipartite graphs remain bipartite after reverse operations, which finishes the problem as trees are bipartite but complete graphs are not. Indeed, consider a bipartite graph $H$ with vertices $u$ and $v$ in the same vertex set. If connecting $u$ and $v$ created a $4$-cycle then there would be a path of length $3$ between $u$ and $v$, absurd so we are done.

Let $G_n$ be the graph formed in the end upon which no more operation can be performed. Firstly note that the operation does not disconnect $K_n$ hence $G_n$ is connected.

Very cool problem. In this solution, for vertices $v_1,v_2$, $v_1-v_2$ means that an edge exists between the two vertices The answer is just $n$. We can verify this explicitly for $n=4$, and as a construction for arbitrary $n$, delete all but one edge connected to one vertex, and henceforth ignore that vertex, reducing the answer to that of $n-1$ vertices plus one edge, which works by induction. Now it suffices to show that we can't end up with $n-1$ edges or less. Reverse the problem, so we start with some $k \leq n-1$ edges, and we are allowed to pick some 4 vertices $v_1-v_2-v_3-v_4$ and connect $v_1$ to $v_4$. Clearly this operation doesn't change the connectedness of the graph, so we must start with a connected graph, i.e. $k=n-1$. Then it doesn't contain an odd cycle, so it is bipartite. It is easy to check that adding an edge in the way described preserves the bipartiteness of the graph, as when connecting $v_a$ to $v_d$ with $v_a-v_b-v_c-v_d$, $v_a$ is in the opposite subgraph of $v_b$ is in the opposite subgraph of $v_c$ is in the opposite subgraph of $v_d$ Then we would need the complete graph on $n$ vertices to be bipartite as well if $k=n-1$ worked, but this is absurd: contradiction. Therefore we must start with at least $n$ edges, done. $\blacksquare$

We claim the answer is $n$. We claim that after any number of moves, any two vertices must have an even-length walk between them. Let $A$ and $B$ be two vertices with a walk between them of length $e$, with $e$ even. Suppose one of the edges in that walk is removed in a move. Then, it must be part of a $C_4$. So, in the walk, replace that edge with the other three edges of the $C_4$. Then, there is a walk between $A$ and $B$ of length $e+2$, which is still even. Every pair of vertices has an even length walk between them at the beginning, so they still will after any number of moves. We claim that the lowest number of edges a graph on $n$ vertices with this property can have is $n$. Note that the graph must be connected. Assume towards a contradiction that it has fewer than $n$ edges. Since the graph is connected and has fewer than $n$ edges, it must be a tree. This is because a connected graph has at least $n-1$ edges, and if the graph has a cycle, you can remove an edge and it will still be connected, so a graph with a cycle has at least $n$ edges. However, in a tree, two adjacent vertices do not have an even-length walk between them, a contradiction. Thus, the graph has at least $n$ edges. We claim that there is a graph with $n$ edges that can be obtained from the complete graph after a sequence of moves. Rather than showing how to go from the complete graph to a graph on $n$ edges, we will start with a graph on $n$ edges and show that it is possible to get to the complete graph by adding edges between vertices with a length-3 path between them. This is equivalent, because by playing the moves in reverse, you can get from a complete graph to the graph with $n$ edges. Lemma: If two vertices have an odd-length path between them, by doing reverse moves, it is possible to make them adjacent. Proof: Assume $A$ and $B$ have a path $P$ between them of length $o$, where $o$ is odd. Assume $o>1$. Then, let $X$ be the vertex of $P$ such that the path between $A$ and $X$ on $P$ has length $3$. Construct edge $AX$ if it doesn't already exist. Then, the path with edge $AX$ and the part of $P$ between $X$ and $B$ (if such a part exists) has length $o-2$. So, by doing this process repeatedly, it is possible to make a path between $A$ and $B$ of length $1$. Consider the case where $n$ is odd. Start with a $C_n$. Let $A$ and $B$ be two different vertices. Since $C_n$ has odd length, one of the paths between $A$ and $B$ has odd length. So, by the lemma, it is possible to make $A$ and $B$ adjacent through a sequence of reverse moves. Consider the case where $n$ is even. Let the starting graph have a $C_{n-1}$ and an edge between one of the vertices in the $C_{n-1}$ the vertex not in it. Let $X$ be the vertex not in the $C_{n-1}$, and let $O$ be the vertex it is adjacent to. Using the logic from the $n$ odd case, it is possible to turn the cycle into a $K_{n-1}$. We claim it is also possible to make $X$ be adjacent to any other vertex. Let $A\neq O$ be on the $C_{n-1}$. Then, let $P$ be an even length path between $A$ and $O$. This is possible for any $A$ because the cycle has odd length. Then, the path from $X$ to $A$ including $OX$ and $P$ has odd length. So, by the lemma, it is possible to make $A$ and $X$ adjacent. As previously mentioned, by playing these moves in reverse, you can go from the complete graph to a graph with $n$ edges. Therefore, $n$ edges is both optimal and achievable.

Claim: The graph must always be bipartite Pf: Consider the limiting edge. This can only be removed if there is another edge in the other component, contradiction. $\blacksquare$ This means that there are at least $n$ edges, as else we would have a bipartite spanning tree (the graph must be conected at all times). The construction is straighforward, as we can trim a $K_{n+1}$ to a $K_n$ and a single vertex with degree $1$ and induct down for $n\geq 4$. The base case $n=4$ holds. $\square$

We will solve the problem for all $n\geq3$. We claim that there are at least $n$ edges in the resulting graph. After each operation, the graph is still connected, so the resulting graph must be connected. Now, we claim that it is not bipartite. Before the operation, there exists an odd cycle $A_1$, $A_2$, $\ldots$, $A_k$, $A_1$. If the operation removes the odd cycle, then the cycle of length $4$ must share an edge with this cycle. Assume without loss of generality it is $A_1$, $A_2$, $B$, $C$, $A_1$. Then, deleting $A_1A_2$ makes $A_2$, $A_3$, $\ldots$, $A_k$, $A_1$, $C$, $B$, $A_2$ an odd cycle, so it cannot be bipartite. Therefore, the resulting graph is connected and it is not a tree, so it must have at least $n$ edges. Now, we will show that it is possible to get exactly $n$ edges. We will show this by induction on $n$. Base Case: $n=3$ Then, there are three edges in the original graph. Inductive Step: Pick a vertex $A$, and let the other vertices be $A_1$, $A_2$, $\ldots$, $A_{n-1}$. Then, consider the cycle $A$, $A_i$, $A_2$, $A_1$, $A$. Delete edge $AA_i$ for $3\leq i\leq n-1$, then consider cycle $A$, $A_2$, $A_3$, $A_1$, $A$, and delete $AA_2$. By the inductive hypothesis, $A_1$, $A_2$, $\ldots$, $A_{n-1}$ can be turned into a graph with $n-1$ vertices. Therefore, since there is one edge adjacent to $A$, this means that that the resulting graph has exactly $n$ vertices. Therefore, the least number of edges is $\boxed n$.

I had the solution written from a few months ago, but I realized I never posted it here! So here you go: The answer is $n.$ We claim that the operation cannot leave the graph disconnected. When the graph first becomes disconnected, then draw in the last deleted edge $e.$ This is edge was between two points of the same connected component, then adding this edge the graph is still disconnected. Let its endpoints be $v,v'$ where $v,v'$ are from different connected components. Note that $v,v'$ are in a cycle, so there is a path from $v$ to $v'$ not containing $e.$ Thus, removing $e,$ there still exists a path from $v$ to $v',$ contradiction. We claim that the operation cannot remove every odd cycle. Consider the time the graph first becomes bipartite. Then draw in the last deleted edge $e$ which must be within one component of the graph, between say $v,v'$. No other points of this component is connected, and similarly of the other component. Suppose $v,v',w,w'$ is a cycle, then $w,w'$ must be of the other component and connected... contradiction. Now, from those two claims we have the final graph can't be disconnected and it can't be a tree. Thus, it has at least $n$ vertices. Thus, it remains to show that there is always a way to reduce this down to just $n$ vertices. When $n=4$ obviously it works. Suppose it works for $n=k$ then we claim it works for $n=k+1.$ Then pick an arbitrary vertex and all the edges protruding from that vertex. Then, as long as there are at least one such vertex remaining, we can form a 4-cycle. Thus, we leave one such edge, and for the remaining $K_k$ we make it so only $k$ edges remain, and the conclusion follows.

The answer is $\boxed{n}$. Construction. This is by induction. For $n=4$, disconnect $AB$ because of $ABCD$ then $AC$ because of $ACBD$. For $n>4$, choose an arbitrary vertex $P$ and disconnect it from every vertex but one. Now use the inductive hypothesis on the graph besides $P$, and we will have $n-1+1=n$ edges. $\blacksquare$ Impossibility. Note that these operations have to keep the graph connected, so it suffices to prove that the resulting graph is not a tree. Assume FTSOC that it is. Then we can color the vertices of the tree red or blue such that there are no same-colored connections(trees are bipartite). Now I claim that the last same-colored connection(this obviously must exist) should not have been possible to remove. This is because the $4$-cycle, say $ABCD$ with $A$ and $B$ red, must have had $C$ blue and $D$ red, contradiction because then $AD$ is also same-colored. $\blacksquare$

Answer is $n$. Bound: It suffices to show that this graph $G$ remains non-bipartite and connected, as all trees are bipartite. To prove the first claim, note that the last edge removed to make $G$ bipartite cannot be part of an even-length cycle by definition, hence $G$ cannot be made bipartite. On the other hand, as every edge removed is part of a cycle, $G$ remains connected. Construction: Label the vertices $v_1, v_2, \dots, v_n$. For $4 \leq i \leq n$, reverse-inductively remove all edges connecting $v_i$ to $v_j$ for $1 \leq j \leq i-2$ by considering 4-cycles formed in the complete graph $K_{i-1}$. This leaves the graph as a path connected to a triangle, which evidently has $n$ edges.

oo nice problem

Let $G$ be our complete graph. It's obvious that if we apply the operation in $G$, then new graph is still connected. Now assume $G$ is bipartite and we apply operation on $G$ once. Let $H$ be out new graph and assume $H$ is bipartite. Let $(v_{1},v_{2},v_{3},v_{4})$ be a cycle that is chosen and assume we erased edge $(v_{1}, v_{2})$. Let $P_{1}, P_{2}$ be independent sets of $H$. WLOG we can assume $v_{1}, v_{3} \in P_{1}$ and $v_{2}, v_{4} \in P_{2}$. Then $G = H \cup \{v_{1}v_{2}\}$ is bipartite too, a contradiction. Therefore our graph is connected and not bipartite at any moment. Thus at the end it has at least $n$ edges. Now we're construct the order of operations. Let the vertices are $v_{1}, v_{2},\dots, v_{n}$. For $3 \leq i \leq j \leq n$, erase edge $\{v_{i}v_{j}\}$ from cycle $(v_{1}, v_{2}, v_{i}, v_{j})$. For $3 \leq i \leq n$, erase edge $\{v_{3}v_{i}\}$ from $(v_{1}, v_{2}, v_{3}, v_{i})$ and erase edge $\{v_{2}v_{i}\}$ from $(v_{1}, v_{2}, v_{i}, v_{3})$. Therefore our graph has edges $\{v_{1}v_{2}, v_{1}v_{3},\dots, v_{1}v_{n}, v_{2}v_{3}\}$.

Consider reversing the process. Suppose you start with a graph G, and when there exists a path from a node X to a node Y of length 3, you complete the 4-length cycle by connecting X and Y. It can be shown by reversing the sequence of operations that this is equivalent to the original problem. Now suppose you have a graph at the start which is disconnected. Whenever you try to connect vertices from two different connected components, there is no cycle, because to connect X and Y there must be at least some different path from X to Y already. So the connected components stay disconnected from each other, but at the end in the complete graph there is only one connected component, thus this is impossible. Now I will prove that there must be a cycle in the original graph. In the complete graph at the end, there are at least 4 nodes, and since all vertices are connected to each other through edges, there exists three vertices forming a triangle. Without a cycle in the original graph, I will prove that it is impossible for such a triangle to form. Indeed, suppose we want to form the triangle ABC, and we already have the edges AB and AC, so we want the edge BC. For this to happen, we need a 3-length path from B to C, so we had to at some point have a 3-length path from B to C. Suppose that path is BXYC. So we have the 5-cycle ABXYC. If any of the edges in this cycle were created through the given process, completing a 4-cycle, then the other three edges in that 4-cycle must themselves have formed part of this big cycle at some point. Keep doing this until you go back to the starting graph, and it is deduced thusfore that there was always a cycle in the graph: this big cycle. So there must have been a cycle in the original graph. Therefore since there is a cycle, the connected original graph cannot be a tree, so it has to have at least n edges. Indeed, there is a solution with n edges, which can be built up inductively. Here I go back to the problem statement, not the reverse process. Clearly for n=3, the triangle has 3 edges. Now assume that there is a solution for k vertices. If you consider a vertex A of a k+1 vertex graph, and at the start remove each edge from A leaving one behind, these moves are all legal because due to the fact that there is a path between any 2 vertices in the remaining graph, so clearly since n>3 there is a path of length 2 between any 2 vertices in the remaining graph so if we are removing the edge AX, and AY still exists, for any other C, AXCY is a valid 4-cycle which allows us to remove AX. So now there is only 1 edge coming from A. Now for the remaining graph it is possible to do it with k edges, so k+1 edges in total and the statement is proved by induction. The answer is there are at least n edges in the remaining cycle of the graph.

We claim the answer is $n$. This is equivalent to finding the minimum number of edges that we can start with so that we can complete the graph by repeatedly drawing in new edges that finish 4-cycles. First, we will construct $n$. Consider starting with a special vertex $V$ that connects to everything else, and one other connection between vertices $a$ and $b$. Given any edge in the graph not involving $V$, we can draw another edge between one of the two connected vertices to any other vertex, as it completes its 4-cycle with the two vertices and $V$. This allows us to complete the graph (for example by using the first edge to reach all vertices, then completing each vertex separately). Clearly, the graph must start connected, since the operation cannot make a disconnected graph connected. Now, it suffices to show that we cannot complete the graph starting from a spanning tree. The main claim is that upon adding an edge, a bipartite graph stays bipartite. Fix a coloring of red and blue vertices. Note that any new edge added must go from vertices of different colors, since connecting two vertices of the same color cannot complete any 4-cycle in a graph that is already bipartite. Thus, the final graph must be bipartite, so $n-1$ does not work and we are done.

The answer is n. This can easily be checked to work for small values of n. The bound is proven by noticing that the graph will never be bipartate and will always be connected, and hence has atleast n edges. The construction can be done with trivial induction