Solution

(1) All steps are Operation 1 unless indicated.

(2) We will aim for induction.

It's easier to think in reverse. Starting from the target graph with $n$ nodes in a single line:

Reverse of Operation 1: Pick a white terminal node $P$, flip the color of the adjacent node, and then remove $P$.

Reverse of Operation 2: Pick a white intermediate node $P$, flip the colors of the adjacent nodes, and then remove $P$.

With all nodes in a single line, we can unify these two operations by adding auxiliary nodes to both ends. These nodes cannot be operated upon, and the goal is to collapse all nodes except these auxiliary nodes (which do not have to end up white).

When $n = 0$ or $n = 1$ all nodes can be collapsed uniquely.

When $n = 2$, the nodes cannot be collapsed completely.

Now consider the general case with $n$ nodes. Suppose we succeed, and the last node we remove is $P$, with $l$ nodes on the left and $r = n-l-1$ nodes on the right:

This breaks the problem into 2 subproblems of sizes $l$ and $r$ ($0 \leq l \leq n-1$). The order in which we remove the nodes from these subproblems does not matter. The only requirement is that after both subproblems are solved, $P$ must be white; i.e., have been flipped an even number of times.

Based on the small cases, we make a hypothesis:

• If $n = 3u$, then all $n$ nodes can be collapsed, and both auxiliary nodes will always become white (i.e., have been flipped even numbers of times).
• If $n = 3u + 1$, then all $n$ nodes can be collapsed, and both auxiliary nodes will always become black (i.e., have been flipped odd numbers of times).
• If $n = 3u + 2$, then we will fail to collapse all $n$ nodes.

We will prove by induction. The base cases ($n = 0,1,2$) are already proven. For the inductive step, we consider the 3 cases separately. Due to the inductive hypothesis, a subproblem (red or blue) cannot have size $3v+2$.

• If $n = 3u$, we can only have $l = 3v + 1$ and $r = 3w + 1$. This flips $P$ odd + odd = even number of times, and flips both auxiliary nodes odd + 1 = even number of times.
• If $n = 3u+1$, we can only have $l = 3v$ and $r = 3w$. This flips $P$ even + even = even number of times, and flips both auxiliary nodes even + 1 = odd number of times.
• If $n = 3u+2$, one of $l$ and $r$ must be $3v$ and the other must be $3w+1$. This flips $P$ even + odd = odd number of times, and thus we will always fail to collapse all nodes.

Therefore, all $n$ nodes can be collapsed if and only if $n \not\equiv 2 \pmod 3$.

Epilogue

The original problem statement is very verbose, making it look deceptively scary. On top of that, the book uses group theory to prove (2), which makes the problem look even scarier. (Well, the solution above also uses ideas from group theory without referring to group theory.)

As a sidenote, here is International Mathematical Olympiad 2005 Shortlist, Problem C5:

There are $ n$ markers, each with one side white and the other side black. In the beginning, these $ n$ markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if $ n - 1$ is not divisible by $3$.

It's exactly the same problem! Somehow it managed to get into the shortlist.