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.