Quick proof-by-contradiction of @David's "cool little theorem" above (#21):

Suppose we have a set \\(X\\) and two equivalence relations on it, red and blue, whose union is the total relation on \\(X\\). In other words, any two nodes in \\(X\\) are either red-linked, or blue-linked, or both.

Suppose further than neither red nor blue are total. Then we can find nodes \\(A\\) and \\(B\\) that are not red-linked (so must be blue-linked), and nodes \\(C\\) and \\(D\\) that are not blue-linked (so must be red-linked).

Now consider \\(AC\\) and \\(BD\\). If both are red, we have \\(A \text{ red } C \text{ red } D \text{ red } B\\) – contradiction. If both are blue, we have \\(C \text{ blue } A \text{ blue } B \text{ blue } D\\) – contradiction.

If \\(AC\\) is blue and \\(BD\\) is red, consider \\(AD\\). If \\(AD\\) is red, we have \\(A \text{ red } D \text{ red } B\\) – contradiction. But if \\(AD\\) is blue, we have \\(C \text{ blue } A \text{ blue } D\\) – contradiction.

If \\(AC\\) is red and \\(BD\\) is blue, consider \\(BC\\) – by a similar argument, this can't be red and can't be blue.

So any which way leads to a contradiction, hence either the red or the blue relation was already total.

Suppose we have a set \\(X\\) and two equivalence relations on it, red and blue, whose union is the total relation on \\(X\\). In other words, any two nodes in \\(X\\) are either red-linked, or blue-linked, or both.

Suppose further than neither red nor blue are total. Then we can find nodes \\(A\\) and \\(B\\) that are not red-linked (so must be blue-linked), and nodes \\(C\\) and \\(D\\) that are not blue-linked (so must be red-linked).

Now consider \\(AC\\) and \\(BD\\). If both are red, we have \\(A \text{ red } C \text{ red } D \text{ red } B\\) – contradiction. If both are blue, we have \\(C \text{ blue } A \text{ blue } B \text{ blue } D\\) – contradiction.

If \\(AC\\) is blue and \\(BD\\) is red, consider \\(AD\\). If \\(AD\\) is red, we have \\(A \text{ red } D \text{ red } B\\) – contradiction. But if \\(AD\\) is blue, we have \\(C \text{ blue } A \text{ blue } D\\) – contradiction.

If \\(AC\\) is red and \\(BD\\) is blue, consider \\(BC\\) – by a similar argument, this can't be red and can't be blue.

So any which way leads to a contradiction, hence either the red or the blue relation was already total.