Consider what happens if both Abraham and Benjamin send to Computer O a permutation calculated as follows:

- First, place all
*x*in the*x*'th place, for values of*x*within the set. (For Abraham: in Abraham's set; for Benjamin: in Benjamin's set.) - Next, place each remaining
*x*in the next available space after the*x*'th place (in cyclic order).

It would have been nice if there had been exactly one cycle in the case of no commonalities, but this is not quite the case. Let us analyze the combined permutation on the assumption that the two sets have no element in common.

Let us consider the problem as a graph problem. Let
*G*=<*L*,*R*,*E*> be a directed bipartite graph, with
*L*={*l*_{1},...,*l*_{n}} and
*R*={*r*_{1},...,*r*_{n}}. There is an
edge in *G* from *l*_{i} to *r*_{j}
if and only if Abraham's permutation maps *i* to *j*. Similarly,
there is an
edge from *r*_{i} to *l*_{j}
if and only if Benjamin's permutation maps *i* to *j*.

The combined permutation *A*ο*B* describes how elements in
*R* map to other elements in *R* through elements in *L*. If
this combined permutation is cyclic, the graph *G* is connected, and
vice versa.

Note that by construction *G* has at most one edge
from *l*_{i} to *r*_{j} with
*i*>*j* and, for the same reason, it has at most one edge
from *r*_{i} to *l*_{j} with
*i*>*j*. Except for the two special elements that are
the targets of these two edges, each element,
on either side of the graph, must belong to a connectivity component that also
contains a smaller-numbered element. The smallest-numbered element in each
connectivity component must therefore be one of these two special elements.
Consequently, there cannot be more than two connectivity components.

The question remains whether there is one component or two.

Suppose, for the moment, that in addition to there being no common elements,
there is an odd number of elements that are missing from *both* sets.
In particular, there is some *i* for which neither subset contains
*i*.

It is clear that if both *l*_{i} and
*r*_{i} belong to the same connectivity component, this
will be the only connectivity component of the graph. (To see this, simply
renumber the elements *i* to 1, *i*+1 to 2, etc.. In the new
numbering, the two elements *l*_{i} and
*r*_{i} are the two "special" elements.) Note also that if
*j* is the next number (cyclically) after *i* such that *j* is
missing from both sets, *l*_{j} must belong to the same
connectivity component as *r*_{i} and
*r*_{j} must belong to the same
connectivity component as *l*_{i}. This means that the
coloring of elements associated with numbers missing from both sets alternates
in a cycle of length 2. However, because we assumed that their total number is
odd, a cycle of length 2 means a cycle of length 1, meaning that both elements
must belong to the same connectivity component, meaning that there is a total
of a single connectivity component and that the combined permutation
*A*ο*B* has a single cycle.

Let us recap:

- If there are common elements and
*n*>1, Computer O will return "More than one cycle". - If there are no common elements and the total number of elements missing from both sets is odd, Computer O will return "Only one cycle".

This turns out to be fairly easy to do. Suppose *n*_{11} is the
number of common elements, *n*_{10} is the number of elements
only in Abraham's set, *n*_{01} - the number of elements only in
Benjamin's set and *n*_{00} - the number of elements missing
altogether.

We want to calculate the parity of *n*_{00}. Both sides know
the parity of *n*_{00}+*n*_{01}+*n*_{10}+*n*_{11} (this is simply *n*), and both sides can safely
assume that *n*_{11}=0, for the purposes of this calculation.
We can now use the fact that Abraham knows the parity of
*n*_{10}+*n*_{11}=*n*_{10}
(the elements in his subset) and Benjamin knows the parity of
*n*_{01}+*n*_{11}=*n*_{01}
(the elements in his subset). Subtracting the two known parities from
*n* yields the desired parity, given the assumption
*n*_{11}=0.

Abraham and Benjamin can therefore agree on the following protocol to tell them whether their two sets have common elements:

- Step 1: Abraham sends to Benjamin whether 1 is on his list. Benjamin sends to Abraham whether 1 is on his list.
- Step 2: If both have 1, stop. The two sets have commonalities.
- Step 3: Abraham and Benjamin exchange the parities of the number of elements in their respective sets.
- Step 4: If the sum of the parities exchanged is the same as the parity of
*n*, Abraham and Benjamin "tweak" their sets (logically-speaking) as follows: If one of them has 1, that person erases it from his set. If neither has 1, Abraham adds it to his set. (This change doesn't change whether they have commonalities or not, but it does guarantee that if*n*_{11}=0 then*n*_{00}is odd.) - Step 5: Both Abraham and Benjamin calculate order permutations over
[1...
*n*] as described above (if an element exists in the set, the permutation sends it to itself; if it doesn't exist in the set, the permutation sends it to the next one that doesn't exist in the set, cyclically). - Step 6: The permutations are sent to Computer O and the resulting bit is received by both parties.
- Step 7: Stop. If the bit received is "one cycle", there are no common elements. If the bit received is "more than one cycle" common elements do exist.

Interestingly, the fact that Abraham and Benjamin require Computer O's assistance in order to determine in O(1) direct communication whether their two sets have commonalities is a basic result in communication complexity.