Proof

In order to show that the results presented in the paper hold, we need to demonstrate that Discussion. By swapping cells if needed, the algorithm enforces property 1 before each transfer. Since this property supports all the arguments in the proofs, it is sufficient to show that cell swapping operation itself does not break the induction hypothesis of Lemma 3 or the proof of Lemma 1. For this it is enough to prove property 2.

Proof of Claim 1. Consider a cell p presented at input i and destined to output j that is not transferred during a phase. Consider two cases whether another cell is (a) transferred or (b) not to output j.

Case a. Assume that another cell q, less preferred than p by output j, is transferred to j. Otherwise, if q is more preferred than p the property is trivially true. It is easy to see that q cannot belong to i. This is because the algorithm always transfers the most preferred cell to j, and there is at least one more preferred cell (i.e., p) enqueued at i. Consequently q has to belong to another input. Since p is more preferred than q by j, this means that in a previous round, output j made a request to input i, but was rejected (eventually in a subsequent round). The only reason for which this can happen is because during that round input i has granted a request to an output with a more preferred cell than p. Further, in the subsequent rounds of the matching either this request will survive or another one corresponding to a more preferred cell will be granted. Thus, in the end, input i grants a request to an output k which has a cell r which appears before p in the i-th preference list. Let s be the most preferred cell by k enqueued at input i. If s and r do not coincide (i.e., s appears after r in the i-th preference list) they are swapped. Finally, (the new) cell r will be transferred. Since this appear before p in the i-th current preference list the proof for this case follows.

Case b. The proof for this case is similar; if no cell is transferred to j then there was a previous round during which j was rejected by i. Using the same reasoning as above it follows that input i will transfer a more preferred cell than p.

Proof of Claim 2. A swapping operation occurs when an input i grants a request to output j, and when the most preferred cell of j by input i, denoted r, does not coincide with the most preferred cell by output j at input i, denoted s. Note that s appears after r in the i-th preference list; otherwise the two cells coincide and no swapping is required. After r and s are swapped, cell r will inherit the position of s. In addition, since r is less preferred than s by output j, its rank is at least as large as the rank of s. As a result, after swapping, the difference between the rank and the position of the new cell s (i.e., the old r) can not decrease. This concludes the proof. (Note that we are not interested in the new cell r (i.e., the old s), as this cell is transferred to the output during the current phase.)