There are n >= 3 islands in a city.
Initially, the ferry company offers some routes between
some pairs of islands so that it is impossible to divide the islands
into two groups such that no two islands in different groups
are connected by a ferry route.

After each year, the ferry company will close a ferry route between
some two islands X and Y. At the same time, in order to maintain
its service, the company will open new routes according to the following rule:
for any island which is connected by a ferry route to exactly one of X and Y,
a new route between this island and the other of X and Y is added.

Suppose at any moment, if we partition all islands into two nonempty groups
in any way, then it is known that the ferry company will close a certain
route connecting two islands from the two groups after some years.
Prove that after some years there will be an island which is connected
to all other islands by ferry routes.

------------------------

Translate to graph terminology
* At the beginning, there is a connected graph with n (at least 3) vertices.
* a step:
  * take an edge X-Y
  * remove this edge
  * for every Z s.t. X-Z~Y, or X~Z-Y, we add the edge X-Z-Y
    (~ denotes a non-edge)
* condition: for every partition of nodes, an edge between the two parts
  will be used infinitely-many times
* to prove: final state: one node adjacent to everything (and possibly other edges)

Does the step even guarantee that the graph will stay connected?
* If not, then the final state will not be reached, since the operation performs
  inside a single component.
* But it is not immediatelly apparent.
  * X-Y is canceled
  * If there was nothing other adjacent, it would disconnect X and Y
    * however, the graph has at least 3 vertices and is connected at the beginning
      -> there is Z adjacent to WLOG Y
  * X-Y-Z => X-Z-Y
  * So X and Y stay connected

Is the final state actually stable? (if we perform the operation on the final state)
* There is a central node C adjacent to everything.
a) If we cut an edge not touching C, C will keep the property.
b) If we cut an edge X-C, then nor X neither C will have the central property.
  * Could another node gain it?
  * some A adjacent to at least C at the beginning
    * will get an edge to X, but not to the other nodes.
It looks that the final state is not stable. Let's verify it on a concrete example.
 /X
C-Y  cut C-X   C-Y-X
 \Z             \Z/
I got a final state from a non-final state, the final state is not stable.

OK, the graph will stay connected, let's try a few experiments.
If n = 3, there will be always a central node.

If n = 4, start with A-B-C-D
note:
  we can always just try to start with a tree,
    as a tree is really the "worst" case
    -- the step is compatible with the subgraph relation
       if we are removing an edge contained by both graphs
So, A-B-C-D is the only reasonable experiment -- the only tree on 4 vertices without a central node.

Remove A-B
B-C-D
A/
C is central node.

Other attempt:
remove B-C
A-B\
 \C-D
Now, removal of any edge can be interpretted as a subset
of A-B in the initial case.

Note update:
* It is not actually completely true that every graph can be emulated by a tree
  because of the extra condition on the infinite process.
* So the note was actually not correct, and solving it for trees is not sufficient.
* However, starting with trees still look reasonable

One more idea about the stability of the final state:
* could I at least prove that we reach the final state again after breaking it?
* There is no edge X-C, everything else is adjacent to X and Y
a) If we remove an edge X-A (or C-A is symmetric), then
   C-X reappear, and we get the central node again.
b) What if we remove some A-B? (different from C,X)
   ... not much helpful.
* Hopefully, the condition on the infinite process will guarantee us that we will
  take one of the edges X-A or C-A eventually.
  * Let's consider the division to {X,C}, and the rest. The condition tells us exactly what we need.
  * I think that also {X} and the rest would work.

This graph {X,C}-(the rest) contained complete bipartite.
Can I generalise the proof to show that every graph
containing a complete bipartite graph (on its all nodes) will gen to the final state?
Let's have two parts AA -- BB, completely adjacent.
* Due to the condition on the process, we will eventually remove an edge from
  the complete bipartite subgraph.
  A0 - B0
* Then we add edges:
  A0 - Ai for all i != 0
  B0 - Bj for all j != 0
* Then the parts (let a, b denote the sizes of the original parts AA BB)
  {A1 ... A(a-1)} {A0 B0 ... B(b-1)}
  are again completely adjacent.
* Therefore, we decreased the size of the part A by one,
  and we can continue with that until the size of A is 1.

Let's go back to the tree case.
* We remove an edge A-B where A is a leaf.
* Then, A will be newly connected to the nodes behind B.
* If we imagine the tree as being rooted, and connect A only to the parent of B,
  we put A one level up, so it will end up as the root connected to everithing.

Another idea:
What about reaching the final state on less vertices, and then adding a new one.
(that is, solving the problem by induction)

So we assume, that whe problem is already true for n-1 vertices, and we want to prove it for n vertices.
That is, on the n-1 vertices, we get
* central node C
* other nodes A0 ... A(n-2) adjacent to C
* a "new" node X adjacent to at least one of A0 ... A(n-2)
  * (because of connectedness, and if X were adjacent to C we would be done)

To make it hard, let's say X is connected only to A0
(if it is easy and X is adjacent to all Ai's, it is an already discussed case)

Once we will remove the edge X-A0 ... not necessarily.
Group separation: X, {C A0 A1 ... A(n-2)}
So once, an edge between X and one of these nodes will be canceled.
For simplicity, assume now that the C will remain center at the moment
  (so solving just a particular case)
a) If the canceled edge is X-Ai, then Ai is adjacent to C,
   * therefore after the step, C is the global central node.
b) If the canceled edge is X-C, then C was already a global center before.

However, C does not have to be a center, since the final position is not global.
The other option is X C0 C1 A0 A1 ... A(n-3), where every Ci is adjacent to every Aj.
An edge from X is canceled
a) X-C0, after that, X is adjacent to all Aj's, and we have a bipartite case {X C0 C1} {A0 ... A(n-3)}
b) X-A0, after that, X is adjacent to borh Ci's, and we have a bipartite case {C0 C1} {X A0 ... A(n-3)}
both leads to a final position eventually.

Problem Solved!