Parity of the cardinality of an equivalence relation

Question

If $A$ be a set with $|A|=n$. If $R$ is an equivalence relation on $A$ and $|R|=r$, why is $r-n$ always even?

Answer 1

Recall that an equivalence relation is reflexive, symmetric, and transitive. In this case we will only need the first two properties. Reflexivity means that all pairs of the form $(x,x)$, with $x \in A$, belong to $R$. Symmetry means that if the pair $(x,y)$ is in $R$, then $(y,x)$ is also in $R$.

Therefore we can decompose $R$ into two sets of pairs: those of the form $(x,x)$ (the diagonal of $A \times A$), and those of the form $(x,y)$, with $x$ different from $y$. The first subset has cardinality $n$, and the second subset has an even cardinality. Then the result follows.

Note that it is not necessary for $R$ to be an equivalence relation. It suffices that $R$ is reflexive and symmetric.