Combinatorial problems are so famous in IMO nowadays!! BTW why do i think it has something to do with IMO 2007 P3??

The problem is similar to the very famous FST problem that involved friend requests Mr.Chagol wrote: Combinatorial problems are so famous in IMO nowadays!! Yeah actually. And this is a tough one(like every IMO Combi)

Is it true for any $2019$ graph? or just that particular?

mszew wrote: Is it true for any $2019$ graph? or just that particular? Nah. If complete graph, then you're done for. I think the process will involve looking for the minimum number of triangles with missing sides (expected value? Too bad at using it, plus idk if it's even useful) and then the edges just go on decreasing. Obviously sounds too simple for a P3, so I'm missing out on like 99% of the problem.

mszew wrote: Is it true for any $2019$ graph? or just that particular? It heavily depends on the structure of the graph. And you can make deadly mistakes and get yourself deadlocked: Consider a mini-example with only five guys $A,B,C,D,E$ and friendships AB, BC, CD, DA and AE. (1) If you flip the triple ABD, then you generate a 3-clique as component, and you are dead. (2) But if you instead flip the triple ADE, then you can easily reach a situation where everybody has at most one friend.

Suppose that the graph is connected. Is it true that there exists a solution if it is not complete and there exists a vertex with odd degree?

Yes. $\qquad$

Benq wrote: Suppose that the graph is connected. Is it true that there exists a solution if it is not complete and there exists a vertex with odd degree? It seems like it can be solved with tedious caseworks, trying best not to disconnect a component, and playing with some cutedges. If there isn't a better solution, then I'm not sure if it qualifies as a good prooblem for IMO P3.

I'm on mobile right now, but here's the idea of my solution. Hope it works! The graph is connected in the beginning. We will take this component, and always cut 0-2 nodes out of it. Take a spanning tree constructed by BFS at the root R (and do this after each operation). Assume its height is at least 3. If there exists a node A with exactly one child B, do the operation for (A, B, P), where P is the parent of A. Otherwise, there exists a node P with at least 2 children which are simultaneously leaves. Take any A, B of these leaves. If they are not connected, (P, A, B), and otherwise we can do (P, A, P') with P' the parent of P. If height is 2, we proceed similarly, unless the main component is complete. Then, we prove that we can avoid generating a complete graph with at least 4 elements by looking at the situation before this final state. We similarly show that we can avoid a cycle, thus avoiding a complete graph of size 3. @below I had this kind of solution during the contest.

Anyone who solved there at IMO?

Here's a solution

Math-wiz wrote: Anyone who solved there at IMO? Hopefully I did, here’s the idea of my solution: Obviously take the graph whit people as vertices and friendships as edges. I’ll call a complete graph with at least 3 vertices which is disconnected from the rest of the graph a “bad graph”, and a set of vertices whose edges form a cycle and is disconnected from the rest of the graph a “bad cycle”. You can prove that if you get a bad cycle you will get a bad graph, and getting a bad graph is equivalent to “you can’t make All degrees at most one”. So we must avoid bad graphs and bad cycles. Now take all possible sequences of operations you can do with the friendships and terminate any given sequence at the step where one of these three things happen: A- You get a bad graph B- you get a bad cycle C-you can’t do anymore operations and you didn’t have a bad cycle or graph If a sequence of operations ends in C then we clearly win, so suppose for the sake of contradiction that all the sequences end in A or B. Now take the longest running sequence of operations. Take cases wether it ends in A or B then go one step before the termination step. You will find some different operations you can do, and find an even longer sequence of moves from there (just draw the graph and work it out). This is a contradiction. So there exists a sequence of operations ending in C. You can easily check that all degrees must be one then, since there are no bad graphs. Then we are done. We are only to check that in the starting configuration we can make a move. If we cannot make a move the graph must be a bunch of complete graph, which is an easy contradiction with the initial degrees condition.

Call a graph $G$ critical if $G$ is connected, but any legal operation on $G$ results in a disconnected graph. Main claim: If $G$ is critical then $G$ is either a tree, a cycle, or a complete graph.

Now at each point in time, we perform any operation that does not disconnect the graph, until this is no longer possible. (This process terminates since the number of edges is finite and strictly decreasing.) At the end of this process, we obtain a critical graph $T$. Also note that the operations preserve the parity of the degree of each vertex; hence $T$ has 1010 vertices with odd degree. In particular, this means $T$ is not a cycle or a complete graph, ie. $T$ is a tree. Finally, it is easy to see that any operation on a tree splits it into disconnected trees, and we can keep performing the operation around any vertex $v$ with degree at least 2 (ie. on $\{u,v,w\}$ where $uv,vw\in G$). Hence by arbitrarily performing operations on $T$ we end up with a collection of trees such that every vertex has degree at most 1, as desired.

Call a cherry a 3-tuple of vertices $(a,b,c)$ such that $ab, ac$ are edges but $bc$ is not. Let $K_n$ denote the complete graph with $n$ vertices and $C_m$ any connected graph with $m$ vertices with all degrees even. Let's call a graph bad if at least one of its connected components is of the form $K_n$ with $n\ge 3$ or $C_m$ with $m\ge 4$. Let's call a graph good if it isn't bad. Let's call a graph finished if every vertex has degree at most 1. Let's call a graph $G$ a daughter of another graph $G'$ if $G'$ has a move that gives $G$. I prove that our initial graph is good, and moreover that every good graph is either finished or has a good daughter. Since every move decreases the number of edges in our graph, this will clearly finish the problem. Notice every move keeps the parity of the degrees of every edge invariant. So, call a vertex red if it has even degree and green otherwise. The colour of a vertex never changes. First, if our initial graph weren't good then by looking at a connected component that is of the form $K_n$ or $C_m$, the degree conditions imply that in fact we have a $K_{1010}$ or a $C_m$ with all degrees equal to $1010$. In the first case, the rest of the graph can't be completed to be of our desired form, a contradiction. In the second case, clearly $m\ge 1011$ but there are only $1009$ vertices of degree $1010$, a contradiction. So, our initial graph is indeed good. Next, we prove every good graph has a good daughter or is finished. First, notice that the only way to create a connected component of the form $C_m$ is to find a cherry in some connected component which is "holding the component together" (call this a glue-cherry) such that if the move for that cherry is performed, the component splits in two components. If a $C_m$ is obtained then one of these has only red vertices and the other one has a positive even number of green vertices. For contradiction assume $G$ is a good graph with no good daughters that isn't finished. It is easy to see $G$ has cherries and thus it has daughters, all of which must be bad. Take a cherry $(a,b,c)$, and assume we make the move corresponding to it: we get a bad daughter. Call a cherry that isn't a glue-cherry a glue-less cherry. Performing the move for a glue-less cherry necessarily gives either a good daughter or a component of the form $K_n$ ($n\ge 3$). There are 4 cases: CASE 1: A $K_n$ containing $a$ is created, with $n\ge 3$. Say it is $(a,d,e,\ldots)$. Then the only edges in $G$ "leaving" our $K_n$ are $ab$ and $ac$. But performing the move for the cherry $(a,d,b)$ we get a bad daughter which must be a $C_m$ of the form $(caedbf\ldots)$. But it is easy to see that $(a,d,b)$ is glue-less (since $de$ is an edge), contradiction! CASE 2: A $K_n$ containing $b,c$ is created, with $n\ge 3$. Say it is $(b,c,d,\ldots)$. Then the only edges in $G$ "leaving" our $K_n$ are $ba, ac$. If $n\ge 4$, say our $K_n$ is $(b,c,d,e,\ldots)$: then we perform the move for the glue-less cherry $(d,b,c)$, giving us a good daughter, contradiction. Oterwise $n=3$ but the connected component of $a$ in $G$ can't be a $C_4$, and so we have some edge $ae$ with $e\neq b,c$. But then we perform the move for the cherry $(d,b,c)$ (which leaves $d$ isolated). Notice this is a glue-cherry, but it splits into a component that just has $\{d\}$ (this is the component with only red vertices), and into another component that must have green vertices (and isn't a $K_n$ since $eb$ isn't an edge). Thus we get a good daughter, contradiction! CASE 3: A $C_m$ containing $a$ but not $b,c$ is created, with $m\ge 4$. Then $(a,b,c)$ is a glue-cherry, and we get two components $H_1, H_2$, with $a,d,e\in H_1, b,c\in H_2$ where $ad, ae$ are edges in $G$. There are no other edges between $H_1$ and $H_2$ except $ab, ac$. By assumption, $(a,e,c)$ must be a glue-cherry and so in fact $H_1$ splits into $a, H_d$ and $H_e$ and similarly $H_2$ splits into $H_b, H_c$ with the only edges between $H's$ being $ad, ae, ab, ac$ and possibly some other edges from $a$ to $H_d$ and $H_b$. (But by the same reasoning applied to the cherry $(a,d,b)$, we in fact have there are none of these edges.) If $H_e\cup H_c$ is the one with only red vertices, we see that $H_c$ has only red vertices but it has exactly one edge leaving it, $ac$, giving a contradiction via parity of degrees. This is our desired contradiction. CASE 4: A $C_m$ containing $b,c$ but not $a$ is created, with $m\ge 4$. Since $(a,b,c)$ is a glue-cherry, there are no edges leaving $C_m$ apart from $ab, ac$. WLOG we have an edge $ce$ in our $C_m$. Notice some vertex in this connected component of $G$ is green and so $a$ has an edge $af$ with $f$ outside of our $C_m$. Now, perform the move for the cherry $(c,a,e)$: there are two cases. If $c$ has some other neighbour $d$ in $C_m$, then this cherry is glue-less and so performing its move must create a $K_m$, which it clearly doesn't since the number of connected components doesn't change but $f,e$ will be in the same component but not joined by an edge. Therefore, $c$ has no other neighbours and so performing the move for the cherry $(c,a,e)$ will leave $c$ isolated and the other component will neither be a $K_n$ (since $fe$ isn't an edge) not will it be a $C_m$, since there was some green vertex (which can't be $c$, since $c$ at the end is red since it's isolated) in the original component in $G$. Thus is our desired contradiction. CASE 5: A $C_m$ containing $a,b,c$ is created, with $m\ge 4$. But then $(a,b,c)$ was a glue cherry so $a,b,c$ can't all be in the same connected component after performing this move, absurd! Having solved all 5 cases, the problem is solved. $\blacksquare$ EDIT: To the post below: this is accounted for in my solution.

@above What about the graph on 5 vertices formed by gluing two 3-cycles at a vertex? Any valid operation yields a 5-cycle. Edit: In fact any graph whose vertices are all of even degree must reduce to a collection of cycles.

We transform problem condition into graph term as G(V,E). Denote X,Y is the set of user has 1009, 1010 friends. Denote F=friend relation, A'=list frend of A. Now we have 2 crucial claims: Claim 1: Exist 3 people to apply the procedure Proof: Take A in Y hence if exist B in A' not F with all other in A' hence q.e.d. Hence all in A' form a clique so they all in Y. But |Y|=1009<1010 so conclusion. Claim 2: Exist 1 person will have at most 1 friend at graph G' (Delete any isolated vertice) Proof: Assume the contradiction everyone has at least 2 friends. Note that every step reduce 1 edge, by claim 1 it means we can't apply the procedure anymore at turn N>1. Thus we can divide all user into k groups, each group form a clique and 2 distinct group can't connect. Note that 2<=k<=673 because each has at least 3 vertices and we can't have 2019-clique. We can label 2 vertices in order, hence at turn N-1, there must be vertex in group 1 connect with 2 vertex A,B in group 2 and they haven't connected yet. Redo, take another vertex C in the same group with A,B at turn N to apply the procedures at turn N-1. If turn N, C still exist in other group, they musn't connected with A,B. But by previous configuration, they have to be the same groups with A,B,C hence which connected with B thus absurd. This mean by amend move tactic, we can reduce edge until exist one vertice has 1 edge Back to the problem: By claim 2, take that vertice A. If A isolated, ignore A and argue similarly to reduce edge. In contrast, A connect to B, if degB=1 hence we can ignore both, else B still connect with other C. Asume we can't have the conclusion, then we can't reduce edge at turn N. But note that {ABC} can apply, it mean BC must be deleted, which is clearly false with our assumption. Repeatedly that algorithm, we can arrived at situation no one has more than 1 friend, hence q.e.d

@chronondecay: I think that you can slightly shorten your flow of argumentation and skip the corollary (Either $G=C$ or $C$ induces a complete graph in $G$), if you pick $C$ as the shortest cycle in the graph. (1) Note that your lemma (Either $\deg(v)=2$ or $uw\in G$) trivially still holds true for the shortest cycle $C$. (2) If $C$ has a chord, then it is not a shortest cycle. (3) If $C$ has no chord and its length is at least $4$, then by your lemma every vertex on $C$ has degree $2$, and $G=C$. (4) In the only remaining case, $C$ is a triangle and hence a clique of size $3$. Now pick $K$ as the largest clique in $G$, and proceed.

I can smell a good application of CN in it. Not yet sure though.

What do you mean by CN?

After taking the instant at which any one of the operations disconnects the graph $G$, there are several ways of gRiNdInG to show that $G$ is indeed a tree. I just wanted to write how I gRiNd. :V Suppose otherwise, and take the largest cycle $C$ of $G$. If $C$ is not spanning (i.e. not hamiltonian), then due to connectivity, there are vertices $u, v\in C$ and $w\notin C$ such that $uv$ is an edge of $C$ and $vw$ is an edge of $G$. Note that $u$ and $w$ are not adjacent since $C$ is the largest cycle. But then, applying the operation on vertices $u, v$ and $w$ leaves $G$ connected, a contradiction. Hence, $C$ is spanning. Since the operations preserve degree parities, $C$ has a chord $v_iv_j$. Let $v_k$ be vertex adjacent to $v_j$ in $C$. If $v_kv_i$ is not an edge, then applying the operation on $v_i, v_j$ and $v_k$ would leave the graph connected, contradiction. Therefore, by "chain reaction" $v_i$ is adjacent to every vertex of $C$, and hence $v_i$ has degree $2018$. This is obviously a contradiction.

By pigeonhole the graph was originally connected. It's straightforward to see that, if a graph can't be modified through further operations, then it's a union of complete graph connected components. Evidently we didn't start with a $K_{2019}$, so as long as the graph remains connected, we can perform operations. Call user C described in the event a "hinge"; then, as long as the hinge has degree at least $3$, after deleting it we still end up with a connected graph. Suppose that we operate to preserve the connectivity of the graph until we can't anymore. Right before we are forced to disconnect the graph, if it isn't a tree, it must have a cycle of maximal length $C$. Suppose that an edge $ab$ exists with $a\in C$ but $b\notin C$; then, $b$ cannot be connected to either of $a$'s neighbors because doing so forms a longer cycle. Say that one of $a$'s neighbors is $c$; then, we can disconnect $ab,ac$ to join $bc$, contradiction. Hence, before the graph is forcefully disconnected, we have either a cycle of length $2019$ or a tree. But the former case cannot happen since the hinge's degree mod 2 is preserved, so we must have a tree. It's easy to see (say, by induction) that trees can be reduced to disjoint edges, the end.

Take the natural graph theoretic interpretation. Let a move consist of $\{z - x, y\}$ where we delete edges $xz, yz$ and add edge $xy$. Claim 1: The process of applying moves must terminate, and the graph must consist of vertex-disjoint cliques. Proof: Note that each move decreases the number of edges by 1, and hence by Well-ordering of non-negative integers we cannot apply infinitely many moves. Assume we cannot apply another move. Repeatedly apply the following algorithm: 1. Take the vertex with the largest degree, $v_{max}$. 2. All neighbours of $v_{max}$ must be adjacent to each other, otherwise say $x, y$ aren't, then we can apply the move $\{v_{max} - x, y\}$, contradiction. 3. Hence $v_{max}$ and its neighbours form a clique. No vertex of this clique can have a neighbour outside of the clique, otherwise this contradicts maximality of the degree of $v_{max}$. 4. Remove this clique. There are only finitely many vertices but each step removes 1 vertex, hence by Well-ordering again this must terminate. Thus the graph consists of all the removed cliques. $\square$ Let a cycle $c$ have vertices $v_1 - v_2 - ... - v_n$, where $v_i$ adjacent to $v_{i+1}$ and $v_{i-1}$ modulo $n$. Claim 2: If the graph has no cycles, every move preserves this property. Proof: Assume by applying moves we create a cycle from a cycle-free graph. Consider the first move which does this; i.e. before the move the graph is cycle-free, and after it contains a cycle $c$. Each move creates exactly one edge. Hence for this cycle to have not been a cycle beforehand, one of its edges must've been created in the move; otherwise all edges were present before the move and a cycle exists, contradiction. Say $v_iv_{i+1}$ was created by the move $\{x - v_i, v_{i+1}\}$. Hence before the move, $xv_i$ and $xv_{i+1}$ are edges. Case 1: $x = v_j$. Then before the move, since $v_jv_i$ is an edge, we have $v_i - v_j - v_{j+1} - ... - v_{i-1}$ as a cycle, contradiction of minimality of the move. Case 2: $x$ outside the cycle. Then before the move $v_1 - v_2 - ... - v_i - x - v_j - ... - v_n$ is a cycle, contradiction of minimality. $\square$ Let an even vertex be one that starts with degree $1010$, and an odd vertex degree $1009$. Note that parity of the degree is invariant under each move, and hence odd vertices stay odd forever, even vertices even forever. Claim 3: Every even vertex is originally adjacent to at least two odd vertices. Proof: There are $1009$ even vertices to begin with, each with $1010$ neighbours. There are $1009 - 1 = 1008$ possible even neighbours of every even vertex (can't be neighbours with themselves) and so each even vertex has at least $1010-1008 = 2$ odd neighbours. $\square$ Define an O-cycle as a cycle $c$ where $v_i$ is adjacent to $v_j$ iff $|i-j| = 1$ modulo $n$, i.e. it doesn't contain a smaller cycle. Note that 3-cycles are O-cycles by definition. Define a blue cycle to be one with exclusively even vertices, and a red cycle one with exclusively odd vertices. Let a mixed cycle have at least one even and at least one odd vertex. All cycles are either red, blue or mixed. Let a Type 1 cycle be one where there exists a vertex $x$ adjacent to all vertices in the cycle. Let a Type 2 cycle be one where there exists a vertex $x$ adjacent to at least one but not all vertices. Note that if there exists an edge with one endpoint in a cycle and one outside, then the cycle is necessarily Type 1 or Type 2. Let an opp-Type 1 cycle be a red or blue one with an outside vertex adjacent to all vertices in the cycle of the opposite parity to the cycle. Let a set of moves that only remove edges in a subgraph H and leaves the rest of the graph invariant be a H-closed process. Claim 4: For any O-cycle $c$, we can apply a $c$-closed process to reduce it to a 3-cycle. Proof: For $i = n-1, n-2, ..., 3$ in order, do the move $\{v_i - v_n, v_{i-1}\}$. Note that these moves are entirely closed within $c$ and hence don't affect any other edge. We can check that at the beginning, $v_nv_{n-1}$ and $v_{n-1}v_{n-2}$ are edges but $v_nv_{n-2}$ isn't. Hence we can do $i = n-1$. Furthermore after each move $v_nv_i$ isn't an edge, $v_iv_{i-1}$ isn't an edge, and $v_nv_{i-1}$ is an edge. $v_nv_{i-1}$ isn't an edge by O-cycle. Hence we can always do the subsequent moves. We are left with $v_1 - v_2 - v_n$, a 3-cycle. $\square$ Claim 5: We can apply a series of moves from the original graph such that every odd vertex is adjacent to an even one, and vice versa. Proof: By Claim 3, every even vertex is adjacent to at least two odd ones, so there exist at least $1009 \cdot 2 = 2018$ odd-even edges. Consider the original graph. If an odd vertex $v$ isn't adjacent to any even ones, with degree $1009 = 1010-1$ it must be adjacent to all other odd ones. Call such a vertex full. Now repeatedly apply the following algorithm: 1. Assume every odd vertex not adjacent to any even one is full, and there are $2018$ odd-even edges. Assume every even vertex is adjacent to an odd one. 2. Consider any full odd vertex $v$. 3. By Pigeonhole, there exists an odd vertex $x$ adjacent to at least two even vertices, $y_1, y_2$, otherwise at most there are $1009$ odd-even edges, contradiction. 4. $v$ must be adjacent to $x$ since it is full; hence we can apply $\{x - v, y_1\}$ to get $v$ adjacent to $y_1$. 5. Note that $vy_1$, $xy_2$ are odd-even edges; we've preserved the property that every even vertex has an odd neighbour. Furthermore we preserve the property that odd vertices already with an even neighbour have an even neighbour, and instead give a previously full vertex an even neighbour. 6. In the move we remove one odd-even edge but create one, so the number of odd-even edges is invariant. Note that this algorithm increases the number of odd vertices with an even neighbour by 1, and so eventually terminates since there are finitely many odd vertices. $\square$ Claim 6: Given a Type 2 O-cycle, we can apply a $c$-closed process to remove all edges in $c$. Proof: By hostile neighbours, WLOG $x$ is adjacent to $v_1$ but not to $v_2$. Apply Claim 4 onto $c$ to get the 3-cycle $v_1 - v_2 - v_3$. Now do $\{v_1 - v_2, x\}$, $\{v_3 - v_1, v_2\}$ and finally $\{v_2 - v_1, x\}$. Note that the neighbours of $x$ are invariant but all edges in $c$ are deleted. $\square$ Claim 7: A mixed O-cycle $c$ is Type 2. Proof: Consider odd vertex $v_i$ in $c$. It cannot have all neighbours in $c$, as it only has 2 neighbours in $c$ and 2 is even. Hence, there exists $x$ outside $c$ adjacent to $v_i$, and $c$ is either Type 1 or Type 2. If $c$ is Type 1, every vertex $x$ adjacent to some vertex in $c$ is adjacent to them all. Hence all vertices in $c$ must have equal degree. But they don't as there are odd and even degrees, so $c$ is Type 2. $\square$ Claim 8: Given that all vertices have a neighbour of the opposite parity, any O-cycle is either Type 1 or Type 2. Proof: Case 1: A vertex has its opposite parity neighbour in the cycle. Then the cycle is a mixed O-cycle and is Type 2 by Claim 7. Case 2: A vertex has its opposite parity neighbour outside the cycle. Then it is either Type 1 or Type 2. $\square$ Now we construct an algorithm to remove all cycles from the original graph. Repeatedly apply the following: Step 1: Clean-up. Given that every red or blue O-cycle is either opp-Type 1 or Type 2, repeatedly apply the following algorithm: 1. Take the smallest red or blue O-cycle which is Type 2. 2. Apply Claim 6 to the O-cycle to remove it. Now all red or blue O-cycles are opp-Type 1. Note that each process only ever removes odd-odd or even-even edges, and hence either breaks a red or blue O-cycle, which is fine, or doesn't affect it. Thus all red or blue O-cycles remain opp-Type 1. Step 2: Cycle removal. Note that each red or blue O-cycle yields a mixed O-cycle, as red or blue opp-Type 1 gives a mixed 3-cycle. Hence, if there are no mixed O-cycles, then there are no red, blue or mixed O-cycles, so no O-cycles. But within every cycle we can find the smallest cycle, which is necessarily an O-cycle. Thus, there are no cycles and we're done. Assume there is a mixed O-cycle. Apply Claim 7 then Claim 6 to remove it. Now there are finitely many red or blue O-cycles. Label them 1, 2, ..., and repeatedly apply the following algorithm: 1. Take the next red or blue O-cycle $c$, with vertices $v_1 - v_2 - ... - v_n$ and outside vertex $x$. It was previously opp-Type 1. 2. If it isn't a red or blue O-cycle anymore, do nothing. 3. Else if it is still opp-Type 1, do nothing. 4. Otherwise, some number of edges from $x$ have been removed. 5. Removing an O-cycle removes at most two edges from each vertex; hence WLOG $xv_1$ still remains an edge, but at least one of $xv_2, xv_3, ..., xv_n$ is destroyed. 6. The O-cycle is now Type 2: use Claim 6 to remove it. Note that each step only ever removes odd-odd or even-even edges, and hence either breaks a red or blue O-cycle, which is fine, or doesn't affect it. Furthermore, this must terminate, and all remaining red or blue O-cycles are either opp-Type 1 or Type 2. Termination We can begin by applying Step 1 because of Claim 5 followed by Claim 8. Step 2 removes at least one edge, and so repeatedly applying the algorithm, it must eventually terminate, either with no edges or no cycles. Either case, the graph is cycle-free. Now by Claim 2, we can continue applying moves until the graph consists of vertex-disjoint cliques by Claim 1. Any clique with size $\ge 3$ warrants a 3-cycle, which cannot exist. Hence only vertices and 2-cliques exist; all vertices have degree at most 1. $\blacksquare$

This is currently my favorite problem from all IMO's! CLAIM:It is possible to make operations, always keeping $G$ connected. Proof: Observe $G$ has always exactly $1010$ odd vertices and $1009$ even vertices. Now consider the largest cycle $C$ in the graph $G$ connected: Case 1: C doesn't have a vertex $v$ of $G$: By maximality and connection, there exists $u\in C$ such that: $v$ is connected to $u$ but not $u+1$ in $C$. Therefore, operate on $(u,u+1,v)$ making the edge $u+1,v$. This clearly still keeps $G'$ connected. Case 2: C is hamiltonian: In this case, by Pigenhole principle, there exists two adjacent odd vertices: $u,u+1$. Consider the next vertex $u+2$ and opperate on $u,u+1,u+2$. The only difference for the graph is that $deg(u+1')=deg(u+1)-2 >0$ since it is odd. This implies that $G'$ is still connected because it contains a cycle through all vertices except $u+1$ and there is an edge in $u+1$. As a conclusion of these steps, we always manage to reduce the graph to a forest. From there, just keep removing the leaves of each tree and we're done.

The key is to keep applying operations while ensuring that the graph is connected. We get ``stuck" in the sequence of operations if we reach a tree (as the remaining graph will be disconnected), a cycle (as one edge must be isolated), or a complete graph (which never appears because the number of edges is decreasing). Notice that reaching a cycle is also impossible, as the sum of the degrees is invariant parity-wise. Now, suppose that we delete an edge from a tree. Then, we obtain a forest because no cycles are possible in the connected components (as they would be cycles in the original graph as well). However, if the forest had any edge of degree $\geq 2$, we can continue the process and obtain yet another forest. This means that if at some point, we reach a tree, we can perform operations such that the condition is eventually satisfied because the number of edges is decreasing. Thus, the main idea is that one can obtain a tree or forest from any connected graph. The main claim is the following: Claim. If a connected graph $H$ is not a tree, a cycle, or a clique, then we can perform a move such that the new graph stays connected. Proof. We take two cases. In the first case, suppose there exists a triangle in $H$. Consider the maximal clique in $H$, which we will call $K$. Then there exists $x \not \in V(K)$ and $a \in V(K)$ such that $a$ is adjacent to $x$. By maximality, $K \cup \{x\}$ cannot be complete, there exists a vertex $b \in V(K)$ such that $b$ is not adjacent to $x$. Then, perform an operation on $a, b, x$; we know we can travel between $a$ and $b$ via some intermediate vertex in $K$ (which is connected by the definition of a complete graph.) Furthermore, we can travel between $a$ and the rest of the graph as well, so we are done. The second case is where there are no triangles in $H$. Pick a minimal cycle $C$ in $H$ (as $H$ is not a tree). Then, there exists some $a \in V(C), x \not \in V(C)$, such that $a, x \in E(H)$ because $H$ is not a cycle. Pick another $b$ connected to $a$ in $C$; we know that $bx$ is not an edge because there are no triangles. Then, perform an operation on $a, b, x$ as before; the resulting graph is still connected because we can travel $a \to b$. Thus, we are done. $\blacksquare$ Finally, because any connected graph with 2018 edges must be a tree, we will eventually obtain a tree upon applying such moves. From there, we can always obtain the desired condition by previous discourse.

Let people be vertices, and draw edges between two vertices if they are friends Claim: The graph is connected Proof: Consider any two vertices $x$ and $y$ in the graph, If there is an edge connecting $x$ and $y$ we are done Hence, suppose otherwise. Observe $\deg(x) + \deg(y) \geq 1009 +1009 =2018$ but there are $2017$ vertices excluding $x$ and $y$, which implies that $x$ and $y$ must share a common friend implying connected Now, keep carrying out the operations while ensuring all the vertices are connected. Consider when no more such operations exist Case 1: The resulting graph is a tree Operate on any vertex on the tree Observe that an operation splits a single tree into two disjoint trees Also observe that there always exists an operation if the number of vertices on the tree $\geq 3$ Hecne, we can continue operating until $\deg v \leq 1$ for all vertices $v$ Case 2: The resulting graph is not a tree Note that there must clearly exist a cycle in the graph Consider the shortest cycle in the graph (if there are multiple just choose any one) Nore that a vertex in the cycle is connected to exactly two other vertices in the cycle. If not, there exists a shorter cycle, contradiction Case 2.1 The smallest cycle has $\geq 4$ vertices Claim: The graph must be a cycle FTSOC, suppose otherwise, Then there must exist a vertex $v$ in the graph not in the cycle but connected to some vertex $x$ in the cycle Suppose the vertices adjacent to $x$ in the cycle is $m$ and $n$ If $v$ shares an edge with $m$ or $n$ $v,m,x$ or $v,n,x$ is a cycle of length $3$ which is smaller than the current cycle , contradiction If $x$ does not share an edge with $m$ or $n$ Take $v,x,m$ and operate. Observe that it is connected. But by assumption, such an operation cannot exist , contradiction Hence, our claim must be true Now, our graph is a cycle. Simply choose any 3 consecutive vertices and operate. This results in a vertex with $\deg 0$ and all other vertices to remain in a cycle Reapeating this, all vertices except two have degree $0$ Case 2.2 The smallest cycle has $3$ vertices Note a cycle with $3$ vertices is $K_3$ Which implies that there exists at least one clique in the graph Consider the clique in the graph with the largest number of vertices (if there are multiple, simply choose one) Subclaim: The graph is not a clique Proof: We have $2019$ vertices For it to be a clique, all have $2018$ friends, but this is clearly not true Every operation monovariantly decreases the number of edges, which means at no point is the graph a clique Using our subclaim, there must exist a vertex $v$ not in the maximal clique Such that there exists a vertex $x$ in the maximal clique sharing an edge with $v$ If there exists a vertex $u$ in the clique such that $u$ does not share an edge with $v$, Operating on $v,u,x$ will still result in a connected graph, contradiction Which implies all vertices in the maximal clique share an edge with $v$ Implying that there exists a large clique with $v$ , contradiction Hence, a smallest cycle with $3$ cannot exist.

Assign to each user a vertex of graph $G.$ Two vertices are connected if respective users are friends. Note that events (operations) preserve a parity of degree of each vertex, so we always have exactly $1010$ vertices with odd degree. Claim. $G$ is connected. Proof. Assume there are two unconnected parts. They include vertex of degree at least $1009,$ so they both have at least $1010$ vertices, contradiction $\Box$ Claim. If $G$ is not a tree, we may apply operation in such way, that $G$ remains connected. Proof. Pick the maximal simple cycle $C.$ If there there are vertices in $G\backslash C,$ then there exist adjacent $X,Y\in C$ and $Z\in G\backslash C$ such that $XZ$ is the edge and $YZ$ is the anti-edge, and it's clearly suffice to apply operation on triple $XYZ.$ If $C$ contains all vertices of $G,$ then by Pigeonhole principle it contains two adjacent vertices $P,Q$ with both odd degrees; if $R$ is the second vertex adjacent to $Q$ in $C$ and $PR$ is the anti-edge, then we apply operation on $PQR$ $-$ since $Q$ still has odd degree, it is connected with cycle passing through all other vertices of $G;$ otherwise consider the next vertex $S$ after $R$ in cycle; if $PS$ is the anti-edge we apply operation to $PRS,$ otherwise go next; if we never stopped, then $\deg P=2018,$ contradiction. This completes the proof of claim $\Box$ Each operation decreases number of edges by $1,$ so applying them in style of second claim we reduce $G$ to a tree. Notice that operation can't create a new cycle in graph, so after this point we will always obtain a forest, while we can apply the operation. The only case when we can't continue is the required situation, thus we are done.

In general, refer to the event described in the problem as a move in graph-theoretic context. Claim: For any connected graph $G$, there exists a move such that when applied, $G$ remains connected, unless $G$ is a clique, a cycle, or a tree. Proof: Let $\mathcal{C}$ be the minimal cycle of $G$. If $\mathcal{C}$ does not have period $3$, then take $b$ such that $d(b, \mathcal{C})=1$ and $b \not\in V(\mathcal{C})$, and let $a \in V(\mathcal{C})$ be the vertex with $d(b, a)=1$. We can perform a move on $abc$, which preserves the connectedness of $G$. Suppose that $\mathcal{C}$ has period $3$. Now let $\mathcal{K}$ be the largest clique in $G$. Take $b$ such that $d(b, \mathcal{K})=1$ and $b \not\in V(\mathcal{K})$, and let $a \in V(\mathcal{K})$ be the vertex with $d(b, a)=1$. Note that $\mathcal{K} \cup \{b\}$ is not complete due to maximality. Thus, we can similarly pick $c \in V(\mathcal{K})$ different from $a$ satisfying analogous conditions. We can perform a move on $abc$, which preserves the connectedness of $G$. We are done. $\square$ Let $G$ be the natural graph formulation of the network given in the problem. We can keep on applying moves generated by the claim until the claim is inapplicable. Obviously $G$ is not a clique, so after any number of moves it cannot be a clique. $G$ cannot be a cycle because cycles have degrees all even, and moves preserve parity of degrees, so $G$ cannot become a cycle after any number of moves. For two distinct vertices $a$ and $b$, let $n$ be the number of their common neighbors. Then, $\deg(a)+\deg(b)-n$ is the number of vertices that are a neighbor to at least one of $a$ and $b$, and thus at most $2019-2=2017$. Since $\deg(a)+\deg(b) \ge 2018$, $n \ge 2018-2017=1$, so $G$ is connected. Hence, we can find a sequence of moves such that when applied, the result is a tree, as desired. $\blacksquare$

Let $G$ be the graph where vertices correspond to users, and two users who are friends correspond to an edge in the graph. We claim that if $G$ is connected and has a cycle, then it is always possible to cause events that maintain the connectivity of $G$. In the beginning, if $G$ were disconnected into two or more connected components, both components have at least $2010$ vertices, contradiction. Thus, $G$ starts connected. Note that $G$ always has $1010$ vertices of odd degree and $1009$ of even degree because events don't change degree of vertices. Consider the longest non-self-intersecting cycle $V_1\to V_2\to \dots\to V_{n}\to V_1$. Suppose $V_{n+1}$ is not in the cycle. Then, of course our assumption is that the graph was never disconnected to begin with. Let $V_{n+1}$ be connected to $V_x$ then let the event happen on $V_{n+1},V_x,V_{x+1}$. If $V_{n+1}$ and $V_{x+1}$ are connected, then there is a bigger cycle. Clearly, this creates the path \[V_{x-1}\to V_{x-2}\to \dots\to V_{1}\to V_n\to \dots\to V_{x}\to V_{n+1}\]and so no disconnections happened. If the graph passes through every vertex, then there are two odd-degree vertices that are adjacent, $V_x$ and $V_{x+1}$. We find the minimum value $t$ such that $V_{x+t}$ is not connected to all of $V_{x},V_{x+1},\dots,V_{x+t-1}$. Then, if it is not connected to $V_{x+i}$ then do the event on $V_{x+i},V_{x+t-1},V_{x+t}$. If no such $t$ exists, we have a clique, absurd. Since we only ever decrease the number of edges, we can continue apply this operation until there are simply no cycles left. We have a tree, and so we can simplify the tree little by little by operating on length $3$ paths originating at a leaf.

Take the obvious graph-theoretic interpretation. I will prove that any connected graph that either has an odd-degree vertex and is not a $K_n$ for $n \geq 3$, or is an isolated vertex, can be reduced to a graph whose connected components are either isolated vertices or two vertices connected with an edge; this is by induction on $V+E$ with base cases (isolated vertex and $K_2$) trivial. Call such graphs good. Refer to moving on $(a,b,c)$ as removing $\overline{ab}$ and $\overline{ac}$ and adding $\overline{bc}$. Moves clearly preserve the parity of the degree of every vertex. Consider a good graph $G$. First suppose that some move $(a,b,c)$ can disconnect $G$ into two non-isolated components $G_1 \ni b,c$ and $G_2 \ni a$. Thus there must exist vertices $v_1,\ldots,v_k$ adjacent to $a$ that end up in $G_2$. Suppose we delete $a$ and two $v_i,v_j$ are still connected (where $i \neq j$). Then move on $(a,b,v_i)$, which preserves the connectivity of the graph and thus the goodness (since degree parity is preserved and the result clearly isn't a complete graph). If we delete $a$ and $b,c$ are still connected, then move on $(a,b,v_i)$ where $i$ is arbitrary which preserves goodness similarly. Otherwise, deleting $a$ will split every vertex $v$ adjacent to it into its own connected component $\mathcal{C}_v$ (at least $3$ of them). Now move on $(a,b,c)$ anyways. This disconnects $G$, but I claim that the two resulting components are still good. Indeed, $\mathcal{C}_b$ has an even number of odd-degree vertices, so adding the edge $\overline{bc}$ gives it at least one odd-degree vertex. Likewise, $\mathcal{C}_{v_1}$ has an even number of odd-degree vertices, so adding the edge $\overline{v_1a}$ gives it at least one odd-degree vertex. Furthermore, it is clear that the connected component containing $a,v_1,\ldots,v_k$ is not complete unless it's a $K_2$, and the same is true for the connected component containing $b,c$, hence $G$ is split into two good graphs and we can apply inductive hypothesis. Thus suppose no move will disconnect $G$ into two non-isolated components. Take an arbitrary move $(a,b,c)$ and suppose that it leaves a connected component as a $K_n$ for some $n \geq 3$. There must exist some other vertex $v$ in the resulting $K_n$; now move $(a,b,v)$ instead, which clearly preserves the connectivity of $G$ and thus the goodness, since no complete graph can result (specifically, edge $\overline{ab}$ no longer exists) and at least one vertex remains with odd degree, so we can now apply inductive hypothesis. If no such move $(a,b,c)$ exists, then move arbitrarily—note that moves are always possible on non-complete graphs: if $\overline{ab}$ and $\overline{ac}$ being edges always implies $\overline{bc}$ is an edge, then the graph is complete. Either $G$ remains connected, in which case it is good with fewer edges and we can apply inductive hypothesis, or it splits into a non-complete connected component and an isolated vertex. Isolated vertices are good, and the other connected component also still has an odd-degree vertex since the isolated vertex previously had even degree, so we can again apply inductive hypothesis. To finish, note that the original graph has an odd-degree vertex. Furthermore, if it had at least $2$ connected components, some component would have at most $1009$ vertices, but must contain a vertex with degree at least $1009$: contradiction. Hence it's connected, and clearly not a complete graph either, thus good. $\blacksquare$ Remark: It feels like this problem should be rigid: the given condition is too weak to do anything very useful with, and to understand the process better we can try a bunch of small graphs and come up with the characterization of good graphs. The rest is not terribly difficult (even though this solution is inefficient). The hard part is dealing with the possibility of a disconnect but the "obvious" moves work fairly readily.

The worst thing that could happen is if $n$ people were all friends with each other and nobody else. Then, the power of friendship would prevail against the edge-removing operation, putting a stop to our mission of ruining as many relationships as possible. However, this situation is but a speedbump along the road to our final destination. Firstly, the starting conditions given in the problem guarantee that: a) There cannot be a component in the graph that is just $K_i$, and b) No component can have all degrees even. Claim: Consider a component of the graph which is a) not a tree, b) not $K_i$, c) not a cycle (i.e. every vertex has degree 2). We can always make a move within this component that does not split the component into two components. Proof: We split into two cases: this component contains $i \geq 3$ people who are all friends with each other, or it doesn't: If our component contains $K_i$ for some $i \geq 3$, pick the largest possible $i$ for which there exists a $K_i$ in our component. This $K_i$ is not the component itself – therefore, there exists somebody in the $K_i$ (say, Evan) who is friends with somebody outside of this $K_i$ (say, Albert). Albert cannot be friends with every single person in the $K_i$ (since then there would be a $K_{i+1}$ in our component, violating our assumption that $K_i$ was the largest). Let Stanley be somebody in the $K_i$ who Albert is not friends with. We perform the friendship-cutting operation on Stanley-Evan-Albert, severing Evan's friendships with Stanley and Albert. Evan is still part of the component though, since he is friends with the $i-2$ people in $K_i$ who aren't Stanley. [asy][asy] pair A = 3*dir(234); pair B = 3*dir(162); pair C = 3*dir(90); pair Stanley = 3*dir(18); pair Evan = 3*dir(306); pair Albert = (4,-4); dot("Stanley", Stanley, dir(0), black+4); dot("Evan", Evan, 1.5*dir(20), black+4); dot("Albert", Albert, dir(315), black+4); dot(A, black+4); dot(B, black+4); dot(C, black+4); draw(A--B--C--Stanley--Evan--A--Stanley--B--Evan--C--A); draw(Evan--Albert); [/asy][/asy] If our component doesn't contain $K_i$ for any $i \geq 3$: we're assuming our component isn't a tree, so there's some cycle. We're also assuming our component doesn't have every vertex with degree $2$, so somebody in the cycle (say, Anish) must be friends with somebody not part of the cycle (say, Celine). Let Ronald and Alex be the two people adjacent to Anish in the cycle. Celine can't be friends with Ronald (or Alex for that matter) since then Celine, Ronald and Anish would all be friends with each other – $K_3$. We perform the friendship-cutting operation on Ronald-Anish-Celine, severing Anish's friendships with Ronald and Celine. Anish is still in the component since he's friends with Alex; Ronald is friends with somebody else from the cycle. [asy][asy] pair X = (0,0); pair Y = (2,0); pair Alex = (3,2); pair Ronald = (-1,2); pair Anish = (1,3); pair Celine = (1,5); dot("Alex", Alex, dir(0), black+4); dot("Ronald", Ronald, dir(180), black+4); dot("Anish", Anish, 2.5*dir(270), black+4); dot("Celine", Celine, dir(90), black+4); dot(X, black+4); dot(Y, black+4); draw(Celine--Anish--Ronald--X--Y--Alex--Anish); [/asy][/asy] Our claim is proved. $\square$ The way the friendship-severing operation is defined, the parity of the degree of each vertex is always fixed; we're given that no component begins with every vertex having an even degree, and the processes we described above won't change that. Thus, in either case above, after performing the friendship-severing operation, we can still be sure that not every vertex has degree $2$. Furthermore, because our process does not split a component into two, we will never be left with a component that's just $K_i$; our process preserves the number of vertices in the component while decreasing the number of edges. (This is the whole motivation for coming up with this process.) However, our process could turn a component into a tree, which means we can't repeat the process on that component anymore. So, we perform the process described above on each component of our graph until every component is a tree; then, we carelessly perform the friendship-splitting operation on each tree, since that turns a tree into smaller trees. Once we can't do this anymore, all of our trees have at most $2$ vertices, which is what the problem asked for. edit: bruh i didn't realize the conditions also just imply the graph is connected.... that doesn't seem to be necessary though?

I claim that a sequence of moves is possible if all the components of the given graph that have at least $3$ vertices are not cliques and have at least one vertex of odd degree. Since the smallest component of the starting graph has at least $1010>2019/2$ vertices, it's connected, and as it has a vertex of odd degree, the problem follows from the claim. We use induction on the number of edges, with the base case (no moves possible) tautological. It suffices to show that there exists a move retaining the condition. Indeed, choose a move arbitrarily with users $A$, $B$, and $C$. There are a few cases in which this move creates a new graph that breaks the conditions. (Note that all of these cases increase the number of components, as the parity of the degree of the vertices is fixed and it is impossible to create a clique by removing an edge.) We will show that in all cases, there exists another move that works. The first case is when the move results in $A$ being isolated, but $B$ and $C$ become part of a clique with an additional vertex $D$. Instead, operate on $A$, $B$, and $D$. The other case is when $A$ disconnects from $B$ and $C$. Since $A$ cannot now be isolated (or otherwise the conditions are still met), $A$ is adjacent to another vertex $D$. Clearly $D$ is not adjacent to $B$ or $C$. Now, if operating on $A$, $B$, and $D$ or $A$, $C$, and $D$ does not disconnect the graph, use one of these moves. Otherwise, removing $A$ in the graph results in three components containing $B$, $C$, and $D$. Take (WLOG) the component with $B$. If all vertices have even degree, then $B$ has odd degree if you include the edge $AB$. Otherwise, at least two vertices have odd degree and so adding back the edge $AB$ there's still one vertex with odd degree. Thus, both of the components of the original move satisfy the condition and we're done!