Define a wazoo as a partition of the islands into groups $A$, consisting of two islands, $B$, consisting of all islands connected by ferry route to both islands in $A$, and $C$, consisting of all islands not connected by ferry route to either island in $A$. Define the size of a wazoo as the number of islands in $A$ and $B$. Note that after any year, we will have a wazoo consisting of all of the islands with $A=\{X,Y\}$. After each year, the company will apply the operation to one of (i) an island from $A$ and an island from $B$ (ii) two islands from $B$ or two islands from $C$ (iii) an island from $B$ and an island from $C$. We will deal with those cases separately: (i) Suppose that $A=\{v_1,v_2\}$ and $B=\{w_1,w_2,\ldots,w_k\}$ and that the company applies the operation to $v_1$ and $w_1$. Then, note that as $v_2$ and $w_1$ are connected before the operation, $v_2$ will be connected to both $v_1$ and $w_1$ after the operation. Also, as $v_1$ is connected to $w_2,\ldots,w_k$ before the operation, both $v_1$ and $w_1$ will be connected to $w_2,\ldots,w_k$ after the operation. Hence, we will have a new wazoo with $A=\{v_1,w_1\}$ and $\{v_2,w_2,\ldots,w_k\}\subset B$, so we switch focus to this wazoo, with its size nondecreasing. (ii) This cannot delete or add routes between islands in $A$ and other islands, so our wazoo is unaffected and its size remains the same. (iii) Suppose that the company applies the operation to islands $b\in B$ and $c\in C$. As $b$ is connected to both islands in $A$ before the operation, both $b$ and $c$ will be connected to both islands in $A$ after the operation. Furthermore, no other routes are added or deleted between islands in $A$ and other islands, so our wazoo increases in size by 1. Thus, if (i) or (ii) ever happens, we preserve the size of our wazoo and if (iii) happens, we increase the size of our wazoo by 1. While $C$ is nonempty, we consider the partition $A\cup B$ and $C$ of the islands. At any time, the company will close some route between $B$ and $C$ after some amount of years as $A$ and $C$ are not connected, whence (iii) will always eventually happen until $C$ is nonempty, at which point we will have two islands $v_1,v_2\in A$ connected to all other islands $w_1,w_2,\ldots,w_{n-2}\in B$. As before, closing routes within $B$ does not affect this full wazoo. At some point, the company will close a route between $A$ and $B$. Without loss of generality, suppose they close the route between $v_1$ and $w_1$. Then, note that $v_2$ will be connected to all islands after the operation, as desired.

The phrasing of the question is quite difficult to understand. It took me a long time to understand what the question was asking for. I propose an alternative phrasing of the question: You have a connected graph of $n\geq 3$ vertices. Suppose vertices $v_1,v_2$ are adjacent. We define a $v_1-v_2$ operation as follows: 1. Delete away the edge connecting $v_1$ and $v_2$. 2. For any vertex $u \neq v_1,v_2$, if $u$ is adjacent to $v_1$ or $v_2$, it becomes adjacent to both of them. Every second, an operation is done. Suppose at any moment, for any partition of the vertices into nonempty sets $A$ and $B$, there exists vertices $a \in A$ and $b \in B$ such that operation $a-b$ will done some time in the future. Prove that at some point in time there is a vertex of degree $n-1$. My solution: Call a set of vertices $V \subseteq G$ good if there exists a partition of $V$ into nonempty sets $A,B$ such that for every $a\in A$ and $b\in B$, $a$ and $b$ are adjacent. (Basically this is the existence of a spanning complete bipartite subgraph.) It can be shown that a good set of vertices will always remain good. Call the score of a graph to be the size of the largest good set. Since good sets can never be destroyed, the score never decreases. So there exists a point where the score stops increasing. Suppose this corresponds to a good set $V \neq G$. Then by partitioning the vertices into $V$ and its complement, there must exists vertices $a \in V$ and $b \notin V$ where an $a-b$ operation is done. It can be checked that $V \cup \{b\}$ is now a good set. Therefore at some point in time $V=G$. It is easy to finish off from here.

Interpret what the problem says as a graph in the obvious way. Trough the first condition and simple case checking we deduce that this graph is always connected. For two vertices $a, b$ let the set of vertices that are adjacent to both, $a$ and $b$ be referred to as the sprout $S(a, b)$. We show that the size of the maximal sprout never decreases, and that it increases eventually as long as it is smaller than $n - 2$. To show the first claim, consider a sprout $S(a, b)$ of maximal size. The size of this sprout obviously never decreases until an operation involving $a$ or $b$ and a vertex $v \in S(a, b)$ happens. WLOG let this operation be on the edge $av$. At this point every vertex in $(S(a, b) \setminus {v}) \cup \{u\}$ must become adjacent to both $a$ and $v$ so that $S(a, v)$ now has a size at least as great as that of $S(a, b)$. We now prove that the size eventually increases. Assume that the maximal size of a sprout at some point is $k \leq n - 3$. Call a set of $m \geq k + 2$ vertices $k$-sweet if it is possible to partition it into sets $A, B$ with $|B| = k$ such that every vertex in $A$ is adjacent to every vertex in $B$. We show that eventually, either the size of the maximal sprout increases, or the size of the maximal $k$-sweet set increases. For a $k$-sweet set $T$ partitioned as $(A, B)$ as defined before, call $A$ and $B$ the mantle and the core of $T$ respectively. Assume we have a $k$-sweet set $T = A \cup B$ with $|A| \geq 3$. If an operation between a vertex in $A$ and one in $B$ happens eventually, then let it happen between $u \in A$ and $v \in B$. Every vertex in $(A \setminus \{u\})\cup(B \setminus \{v\})$ will now become a part of $S(u, v)$ and we are done. Thus assume that this never happens. Coupled with what was proven before for $k = 2$ this implies that the size of the maximal $k$-sweet set never decreases. Now use the problem condition with $T$ and $V \setminus T$ to deduce that an operation happens between these sets. Let $r \in T$ and $s \in V \setminus T$ be the vertices involved in this operation. If, at this point, $r$ belongs to the core of $T$, then $s$ will become adjacent to all vertices in the mantle of $T$ and thus choosing any two of them we obtain a larger sprout. If $r$ belongs to the mantle then $s$ becomes adjacent to all vertices in the core of $T$ and thus we may add $r$ to the mantle of $T$. Thus the size of the largest $k$-sweet set increases. Then eventually we obtain a $k$-sweet set of size $n$. Using the condition with $A$ and $B$ we deduce that an operation will eventually happen between these two sets, contradicting our assumption that it never will. Hence the size of the largest sprout increases and there eventually exists a sprout $S(a, b)$ of size $n - 2$. Finally, apply the condition with $\{a, b\}$ and $S(a, b)$, wlog assume the resulting operation is $av$ for some $v \in S(a, b)$. Then $b$ stays adjacent to every member of $S(a, b)$ and becomes adjacent to $a$ if it wasn't before. We are done.

By the condition, can we assume that there is a route that is closed infinitely many times?

Consider a graph where two vertices are connected iff there exists a route between their corresponding islands. Now, suppose the first route removed is between islands $X$ and $Y$. Once this route is removed, the neighbor sets of $X$ and $Y$ will be identical. Define set $A$ to be this neighbor set, along with vertices $X$ and $Y$, and define set $B$ to be the rest of the vertices. First, consider what happens if a route not containing $X$ or $Y$ is removed, say it was between vertices $V$ and $W$. If neither belong to set $A$, then this move will not impact the neighbor sets of $X$ or $Y$. On the other hand, suppose at least 1 of them is part of set $A$ (WLOG $W$). If $V$ does as well, then nothing pertaining directly to $X$ or $Y$ will change. On the other hand, if $V$ is not part of $A$, then removing route $WV$ will cause $V$ to be connected to both $X$ and $Y$. Essentially, $V$ moves from set $B$ to set $A$. In particular, we see that as long as we don't operate on $X$ or $Y$, their neighbor sets will remain identical, and this common set will only increase. Of course, by the problem condition, we are eventually going to operate on either $X$ or $Y$. (Not both at the same time, since there is no edge connecting them.) WLOG, we operate on an edge $XK$. Now, $X$ and $K$ have the same neighbor sets, and we will define $A'$ and $B'$ similarly to before. First, I claim that $|A'|\ge |A|$. In fact, this is clear since we removed at most one of $X$'s neighbors by this operation (i.e. $K$), however we added back at least one neighbor (i.e. $Y$). As $|A|$ has increased since the beginning, we can say that $X$ has a (not necessarily strictly) larger neighbor set than before. In fact, $A\subseteq A'$. Now, we can continue doing this, and continue altering $A$ and $B$, and it is clear that $|A|$ will always increase. However, as it does not strictly increase, it seems that we may be stuck. But, by the problem condition, we know that as long as $B$ is not empty, there will eventually be an operation between sets $A$ and $B$, and as stated before, this will strictly increase the size of set $A$. Now, these types of operations will continue occurring, each a finite amount of moves after the one before, so eventually $A$ will become the whole set. Suppose the two vertices defining $A$ at that moment are $X_F$ and $Y_F$. Of course, operations not involving these two vertices do not affect their neighbor sets. However, after a finite amount of time, one of them will be operated on (WLOG $X_F$.) At this point, $Y_F$ will connect to $X_F$ without losing any of its neighbors, and will therefore be connected to all other vertices, as desired.

Rephrased problem in GT terms wrote: Geoff has a connected simple graph $G$ on $n\ge 3$ vertices. Every year, Geoff deletes an edge $vw$ from $G$. At the same time, for any other vertex $x\neq v, w$ adjacent to exactly one of $v$ and $w$, Geoff adds an edge between $x$ and the other vertex. Suppose that for any partition of the $n$ vertices into two nonempty groups, Geoff deletes an edge between these two groups infinitely many times (not necessarily the same edge). Prove that eventually there will be a vertex connected by an edge to all other vertices.

Take the obvious graph theoretical interpretation, and call the operation toggling. Call a triple $(a,b,c)$ gud if at least two pairs among them are connected, and call a pair $(a,b)$ gid if there is some $c$ such that $(a,b,c)$ is gud. Note that gud triples always stay gud and hence gid pairs always stay gid. Note that if $(p,q,r)$ is gud and $r-s$ is a toggled edge, then $(p,q,s)$ becomes gud. Hence, if $(q,r)$ is gid and $r-s$ is toggled, then $(q,s)$ is gid. Also, note that after any point, the graph formed by toggled edges is connected. Claim: All pairs are eventually gid. Proof: Fast forward to a point in time after which no more gid pairs are formed. Let $f(u)$ be the set of all vertices that $u$ is gid with, as well as $u$ itself. Note that each $u$ is in $f(v)$ for some $v$, and if $u-v$ is toggled, then since no new gid pairs can be formed, then $f(u)=f(v)$. Thus, by toggled edges forming a connected graph, if the vertices are $v_1,v_2,\ldots,v_n$, \[f(v_1)=f(v_2)=\cdots=f(v_n),\]and since $u \in f(u)$, all of these must be the entire set of vertices, as desired. Claim: All triples are eventually gud. Proof: Basically identical to the previous one. Now, fast forward to a point where all triples are gud. Unless it is a complete graph, we can pick some unconnected pair $(u,v)$. Since $(u,v,w)$ is good for all $w$, both $u$ and $v$ are connected to all other vertices. Now, wait for an edge involving one of $u$ and $v$ to be toggled, and we win.

Very nice problem! Solved with AdhityaMV, mueller.25 Take the obvious graph theory interpretation and call the graph $G$. Let its compliment be $G'$ Claim: If $G'$ is ever disconnected, then we are done. Proof: Look at what the given operation does on $G'$. An edge between two vertices $ab$ is added and for every vertex connected to exactly one of these, remove that edge. Now, consider the number of connected components. Since $G'$ is disconnected, there are at least $2$ call them $A,B$. By the given final condition, eventually we will have to operate on an edge $ab$ with $a \in A$ and $b \in B$. But since there cannot be any vertex connected to both $a,b$, the operation essentially adds $ab$ and destroys every other edge that $a,b$ is connected to. So, $ab$ itself now forms a new connected component. Since this cannot go on forever, we must eventually have an isolated vertex, which is exactly a universal island and so we are done. $\square$ Now, we divide the graph $G$ into three sets $X,Y,Z$ with $X$ consisting of an arbitrary vertex. $Y$ consisting of all vertices adjacent to it and $Z$ having the remaining vertices. $X,Y$ have the property that for any vertices $x \in X$ and $y \in Y$, $xy$ is an edge and also there is no edge between two things in $X$. Call this property niceness If we operate on $xy$, then $y$ is connected to all the remaining things in $Y$ and now $xy$ is not an edge. So, we may move $y$ to $X$ keeping the graph nice. If we operate on $xz$, then again $z$ is connected to everything in $Y$ and so can be added to $X$. If we operate on $yz$, then $z$ is now connected to everything in $X$ because $y$ was, and so we can add $z$ to $Y$ and preserve niceness. Note that operations in the same group dont affect niceness at all. By the final given condition, we know that we must always eventually operate on either $xz$ or $yz$. But this just reduces the number of vertices in $Z$. So, eventually, $Z$ becomes empty. So, we are left with two sets $X,Y$ which are nice. But see that this corresponds to $X,Y$ being not connected in $G'$ and so we are done by the claim. $\blacksquare$

I am not sure whether I understood the problem well but I interpreted the last paragraph as "whenever you partition the vertices into two sets there will be infinitely many moves performed on edges between those two sets", I will call this condition "the condition". I would appreciate if someone checked my solution because it seems fishy to me.

The key is to find the correct invariant. For vertices $u,v$, let $N(u,v)$ be the set of vertices in $V\backslash \{u,v\}$ that is adjacent to at least one of them. Claim: $N(u,v)$ never decreases. Proof: Case 1: $uv$ are adjacent. Then suppose an edge $vw$ is removed, then after that $uw$ will be added if $vu$ are adjacent. Now, suppose $uv$ is removed, then right after, the neighbourhood of $u$ is equal to the neighbourhood of $v$, call $S$. This set will not be updated until the next time the edge $uv$ is removed. If an edge $uj (j\in S)$ is removed, then since $vj$ was previously there, $uv$ will be added. This proves $N(u,v)$ never decreases. Assume $N(u,v)<n-2$, then consider $X=\{u\} \cup \{v\} \cup N(u,v), Y=V\backslash X$. Suppose I toggle $x\in X, y\in Y$ (note $xy$ is an edge so $x\notin \{u,v\}$). Since one of $u,v$ is adjacent to $x$ but neither is adjacent to $y$, this adds $y$ and $x$ is still in $N(u,v)$ as previously proven. This means eventually, $N(u,v)=n-2$ for all $u,v$. This means if there is no edge between $uw$, there is an edge between $vw, vu$ for all $v\notin \{u,w\}$. Toggling any edge between $\{u,w\}$ and $G\backslash \{u,w\}$ works.

We use the obvious interpretation on graph with set of vertices $V$. Call set $U\subset V$ with $|U|>2$ nice if it is a set of vertices of some spawning complete bipartite subgraph. Call operation of removing and adding of edges at the moment as move. Claim 1. Nice set stays nice after any move. Proof. Clearly it's suffice to consider case of removing edge $ab$, where $\mathcal A,\mathcal B$ - bipartition of given nice set, $a\in \mathcal A,$ $b\in \mathcal B$ and WLOG $|\mathcal A|>1.$ Since move makes all vertices from $\mathcal A$ disjoint with $a$, we only need to shift $a$ from $\mathcal A$ to $\mathcal B$ to get the result $\Box$ Claim 2. After some moment $V$ becomes nice. Proof. Pick some nice set $W\subset V$ (which clearly exists) with bipartite parts $\mathcal W_1,\mathcal W_2;$ by assumption some move removes edge between $c\in W$ (WLOG $c\in \mathcal W_1$) and $d\in V\backslash W$ - after this moment $d$ is disjoint with all vertices of $\mathcal W_1$ and so can be shifted to this set. Thus we include vertices from $V\backslash W$ to $W$ one by one, so the conclusion follows $\Box$ Consider moment when $V$ is nice set with bipartition $\mathcal X, \mathcal Y.$ By assumption some move removes edge between $x\in \mathcal X$ and $y\in \mathcal Y$, so all other vertices of $V$ become disjoint with both $x,y.$ Next, some move removes edge between one of $x,y$ (WLOG $y$) and some $z\in V\backslash \left \{ x,y\right \}$ - then $x$ becomes disjoint with $y$, and so $x$ at the moment is disjoint with all other vertices. Done

Sketch of a really long solution: Part 1: Eventually the distance between any 2 points will forever be $\le 2$. Proof: If 2 vertices are close they will always be close. The distancebetween two non-close vertices will never decrease. If there is some vertices $a,b$ with shortest path $a-v_1-v_2-\cdots - v_k-b$ with $k\ge 2$, then we cannot remove any edge between any two vertices in this path. Considering the group of vertices $v_i$, when we remove an edge from $v_i$ to outside, we add another vertex to another shortest path between $a$ and $b$. Eventually every vertex is part of a shortest path, which means we cannot remove any edge containing $a$, contradiction. Part 2: For any 3 points, there is eventually an edge between 2 of them. Proof: consider 3 vertices $a,b,c$ that never have an edge between them. For any other $v$ connected to at least two of $a,b,c$, the edges between $va$, $vb$, $vc$ can never be removed. Similarly, considering the set of all $v$s, we must eventually remove an edge $v_iu$. Then $u$ will now be connected to two of $a,b,c$, so it joins the set. Eventually every vertex is connected to at least 2 of $a,b,c$, which means we cannot remove any edge from the group $a,b,c$, contradiction. Part 3: For any 3 points, there will eventually always be at least 2 edges in them. Proof. Take $a,b,c$ again and suppose otherwise. Suppose it is always 0 or 1. Then for any vertex $v$ connected to all of $a,b,c$, we cannot remove any of $va,vb,vc$. Such a $v$ will eventually exist (if edge $ab$ is removed consider the $v$ connected to $b,c$, if edge $ab$ is never removed we finish in the same way as step 2). Consider the set of such $v$. When an edge $vu$ is removed, $u$ joins the set. Eventually everything is in the set and so we cannot remove any edge from $a,b,c$, contradiction. After that there is only one possible graph, where all vertices have degree $n-2$. Any edge we remove will lead to the desired conclusion. Hence done.

Group solved with leo.euler and blackbluecar. Beautiful problem . Here's what seems to be a new invariant for finishing, considering the neighbors of just one vertex. Call the ferry company Geoff and take the obvious graph interpretation $G$. Claim: Suppose that $\mathcal{P}$ is the minimal path between vertices $a$ and $b$ of length at least $3$. Then deleting any edge in the path decreases the length of the minimal path. Proof. Let the path be $a = x_1, x_2, \dots, x_n = b$. Then deleting the edge $x_ix_{i+1}$ creates edges between $x_ix_{i+2}$ and $x_{i-1}x_{i+1}$ assuming existence, one of which must exist. $\blacksquare$ Claim: Eventually, the distance between any two points in $G$ is at most $2$. Proof. Take points $a$ and $b$. Consider their minimal path $\mathcal{P}$ between them. If Geoff acts on an edge in this path, the minimal distance decreases. Thus, assume Geoff acts only an edge in this path finitely many times, after which he pretends that $\mathcal{P}$ does not exist to get a new graph $G'$. If no more such paths exist between $a$ and $b$, then this gives a contradiction by taking the partition of $G' = G_1 \sqcup G_2$ into disconnected components. Else, we can consider the new minimal path in $G'$ of $\mathcal{P}_1$. Since there are at most finitely many edges, the result follows. $\blacksquare$ Now suppose that $d(x, y)$ for any $x, y \in G$ is at most $2$. We now define the concept of an almost neighbor. Two vertices $a$ and $b$ are almost neighbors if all of the neighbors of $a$ are neighbors with $b$. Claim: Deleting a connection between vertices $a$ and $b$ turns them into mutual almost neighbors. Proof. Follows by definition. $\blacksquare$ Claim: An almost neighbor to $a$ remains an always neighbor unless becoming a neighbor, which occurs when deleting a vertex connected to $a$ or the almost neighbor. Proof. Let $b$ be an almost neighbor to $a$. This status only changes if Geoff does an operation involving $a$ or $b$, at which point this connects $b$ to $a$. $\blacksquare$ As such, the sum of the number of almost neighbors and neighbors never decreases. Claim: If $a$ has more than one almost neighbor, eventually it has exactly one almost neighbor. Proof. Note that $a$ can only gain finitely many almost neighbor. Then, whenever a deletion involves $a$, this promotes all almost neighbors to neighbors, turning that one neighbor into almost neighbors. $\blacksquare$ Claim: Suppose that $a$ has $k$ neighbors and $l$ almost neighbor such that $k + l < n - 1$. Then the sum of the number of neighbors and almost neighbors eventually increases. Proof. Take $a$, its neighbors, and its almost neighbors as one partition $A$. Eventually some vertex $b$ that isn't a neighbor or almost neighbor has an edge deleted with a vertex in $A$. If it has the edge with $a$ deleted, then the number of neighbors or almost neighbors has increased tautologically. If it has the edge with a neighbor deleted, it becomes a neighbor of $a$. Similarily, if it has an edge with an almost neighbor, it gets connected to all almost neighbors and becomes one itself. $\blacksquare$ Thus, eventually every vertex has at most one almost neighbor and a sum of $n - 1$ almost neighbors and neighbors. If any vertex has zero almost neighbors now, the result follows. Else, suppose that $a$ and $b$ are mutual almost neighbors, and are neighbors with the remaining $n - 2$ vertices. Take a partition of $\{a, b\}$ together and the other vertices by themself. Eventually, a deletion occurs, WLOG let it be between $a$ and some other vertex that isn't $b$. Then $b$ becomes connected with all vertices as desired.

Excellent problem. Solved with a cryptic message from a mysterious source. We take the obvious graph theory interpretation. Call two vertices $x,y$ doppelgangers if $\overline{vx}$ is an edge iff $\overline{vy}$ is. Let the family of this pair be the set of all vertices adjacent to them, along with the two vertices themselves. Observe that after we perform the given operation on two vertices $x,y$, they become doppelgangers, and remain doppelgangers until we perform the operation on one of $x,y$. Moreover, between these two operations, nothing will remove vertices from the family of $x,y$, and if we make a move with exactly one of the vertices in the family of $x,y$ other than $x$ and $y$, the other vertex joins the family of $x,y$. Finally, it is easy to see that when $x,y$ stop being doppelgangers, say by operating on $x,z$, since $z$ is adjacent to $y$ as well (by definition), the new family of $x,z$ contains the previous family of $x,y$. Consider the largest family we ever observe, and suppose it's associated with doppelgangers $x,y$. Between its formation (i.e. when we operate on $x,y$) and dissolution, no moves can occur between this family and vertices not in the family by maximality. When this family dissolves, it's replaced by a new family that must contain the exact same vertices, again by maximality, and again no moves can occur between this new family and vertices not in the family. Thus if this maximal family doesn't contain every vertex in the graph, we contradict the given condition. Therefore, the maximal family contains every vertex in the graph. Consider the move immediately after it's formed, which now must be between exactly one of $x,y$—WLOG $x$—and another vertex. It is then evident that $y$ becomes connected to every vertex, finishing the problem. $\blacksquare$

welp this is basically juts a review of mira74's solution, since it's the closest to my progress self discipline!! need to stop being lazy and pursue the ideas, this was definitely solvable 1) Notice that triangles with at least two edges are preserved. 2) Notice that we are done if all triangles eventually satisfy this property. The point is to prove that all triangles do actually satisfy the property. 3) We need to use the connected graph on toggled edges somehow. 4) Eventually no more triangles are added. The key is that, by the easy visualization of edge contraction, toggling an edge essentially unifies the sets of good pairs (!) This bypasses the more obvious and yet failing approach of simply considering neighborhoods. 5) Take nodes $a,b$ which are connected to $c$ but aren't connected themselves. As it turns out $ab$ is a good pair for $c$, and then we define a set $S=\{c\}\cup \{a,b\}$ consisting of the vertices where $ab$ is a good pair plus $a$ and $b$ themselves. Then toggling edge $uv$ for $u\in S$ and $v\not \in S$ would cause . Wait apparently you're supposed to just do something else: take set $S$ which consists of union of neighborhoods of $a$ and $b$, and notice that toggling an edge from $u\in S$ and $v\not \in S$ will add $v$ to $S$. Then you are done. Wow I need to review this again at some point don't I.

Just a sketch. I did something similar to mira74, but instead of using the 'gid' pairs (which results in a much cleaner solution), I was able to just prove the number of 'gud' triples (triples with at least two edges, note these always remain gud) increases, with a lot of case bashing. Partition into two groups: a vertex (for which there exists non-gud triple) and all the vertices connected to it, and the other group contains all the vertices disconnected from A. Then exploit the fact that every triple containing A in the first group is gud, and case bash to show a new gud triple will be formed.