Pigeonhole principle and the random graph

I have this exercise

(Peter J. Cameron) Prove that for every infinite countable graph $$M$$ the following are equivalent

• $$M$$ is either random, complete or empty (i.e. $$r^M = \emptyset$$, in other words every point is isolated)
• if $$M_1, M_2 \subseteq M$$ are such $$M_1 \sqcup M_2 = M$$ (i.e. they form a partition) then $$M_1 \simeq M$$ or $$M_2 \simeq M$$ (Cameron calls this property Pigeonhole principle)

Now I have some problems in proving this statement. I traced the article (link) by Cameron in which this proposition appears (Prop. 4 page 5) but I'm having a hard time making sense of the proof presented. In particular I don't understand how can we say that $$X$$ and $$Y$$ (defined in the article's proof) form a partition. Any suggestion?

Thanks

We start with two disjoint non-empty subsets $$A$$ and $$B$$ such that $$A\cup B$$ doesn't have a corresponding "correctly joined" vertex in $$\Gamma$$. Then we enhance $$A$$ into $$X$$: a subset of those vertices not in $$B$$ that are not correctly joined with $$A$$. Since we explicitly avoided including $$B$$ vertices in this definition, $$X$$ and $$B$$ are disjoint as well. Now we enhance $$B$$ with vertices not in $$X$$ that are not correctly joined with $$B$$, and get a subset $$Y$$. Again, by this definition, $$X$$ and $$Y$$ are disjoint. Moreover, if we suppose that there is a $$z\in\Gamma$$ which avoided being picked into any of $$X$$ and $$Y$$, then it is correctly joined with both of $$A$$ and $$B$$, which contradicts the initial choice of $$A\cup B$$. Thus $$X\cup Y=\Gamma$$, as required.
Now, by pigeonhole principle, $$X$$ or $$Y$$ is isomorphic to $$\Gamma$$. Taking the isomorhism, say, $$f\colon X\to \Gamma$$, we obtain that $$f(A)$$ is a lesser (than $$A\cup B$$) subset in $$\Gamma$$ that doesn't have a corresponding "correctly joined" vertex. If we took $$A\cup B$$ to be the minimal such subset, we get a contradiction: the only way to avoid this is to assume that the minimal such subset is of size 1 and cannot be split into non-empty $$A$$ and $$B$$, which is handled above in the article proof.
• @FrancescoBilotta it is defined in the paper from the question on page 1: here we take the sets $A$ and $B$ together with some marking of their points in two ways, and correctly joined are those points which are connected to the points marked in the first way, and not connected to the points marked in the second way. Commented Sep 29, 2020 at 16:53