A crazy physicist discovered a new kind of particle which he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(1) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(2) At any moment, he may double the whole family of imons in his lab by creating a copy of each imon . During this procedure, the two copies and become entangled if and only if the original imons and are entangled, and each copy becomes entangled with its original imon ; no other entanglements occur or disappear at this moment.
Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.
Solution
Construct a graph with the imons as vertices, and draw an edge between two imons that form an entangled pair. In addition, we will properly color the vertices. We call a graph good if and only if any two adjacent vertices in have different colors.
1. Lemma. Given an -colored good graph, one can always obtain, through a sequence of operations, an -colored good graph (where ).
Proof. First, we repeatedly perform operation (1) until every vertex has an even degree. This new graph is of course still good.
Next, we perform operation (2); if the original imon has the -th color, then we color the copy with the -th color. It is easy to see that this is still a good graph.
Now, in this new graph every vertex has odd degree, so we can perform operation (1) on all the imons colored with the -th color. Since no two of these imons are adjacent to each other (because the graph is good), by repeatedly performing operation (1) we can remove all imons of the -th color, obtaining an -colored good graph. This completes the proof.
2. Now, suppose there are initially imons; then they must form an -colored good graph. By the lemma above, we can, through a sequence of operations, reduce this to a single-colored good graph, that is, a graph with no entangled pairs at all. This completes the proof.