CONTEXT
Currently I am reading a series of book by Martin Gardner, the one I am working on is "The colossal book of Mathematics". Knowing that this man is hail as the greatest Math-Magician of the 20th Century, I am still surprised by his rather magical tricks.
The following problem is inspired by a Martin Gardner's problem I have read last February.
PROBLEM
Two new-weds are traveling to a group of island that has $2019$ islands in total. Some of the islands are connected by boats, some are not. Any island is linked to at least one other island. The couple plays a game. The husband picks an island they will start and the couple will travel there by airplane. From then on, they will take turns to choose the next island they can travel to using boats and which they have not visited before. Who cannot move anymore loses the game.
Prove that: No matter how the wife moves, as well as how the islands are connected, the husband always has a winning strategy.
EDITS
This problem is just inspired by math tricks, but it is a serious problem. The answer to this may contain graph theory.
Best Answer
@h-sqared and @Robert Israel, you might concern.
So this is my solution to this problem. Please check it out and any comment is appreciated.
Define a set as good if the islands in that set can be divided into pairs, and two island in each pair is connected.
Let $T_M$ be a good set that consists of the most islands. Because we have 2019 islands, which is, obviously, an odd number, so there is at least one island $x$ that does not belong to $T_M$.
Assume that $x$ is linked to another $y \notin T_M$, then we add both $x$ and $y$ to $T_M$, which is a contradition because $T_M$ has already has maximum number of islands.
So $x$ must be only conneted to islands in $T_M$. Now we number the number the islands in $T_M$ in pairs $(a_m,b_m)$ Let the husband start at $x$
Let $x$ conneted with $a_1$. Now the path will be: $x \rightarrow a_1 \rightarrow b_1 \rightarrow a_2 \rightarrow b_2 \rightarrow ... a_k\rightarrow b_k$
If at this point the wife decides to "jump out" of $T_M$, literally move to an island $z$ outside $T_M$ then we swap the pairs from its initial matching to $(x,a_1),(b_1,a_2),...(b_k,z)$. Thus, we now have $T_M$ plus 2 islands that are $x$ and $z$, which is a contradiction.
So the wife cannot jump out of $T_M$. And because the pairs in $T_M$ are matched, no matter how the wife moves, the husband always has another island to go to.
Thus, he wins. Q.E.D