TAOCP 2.3.3 Exercise 7
The relation $9 \equiv 3$ serves only to place the element $9$ into the equivalence class containing $3$.
Section 2.3.3: Other Representations of Trees
Exercise 7. [15] What classes would appear in (12) if the relation 9 ≡ 3 had not been given in (11)?
Verified: yes
Solve time: 1m18s
Solution
The relation $9 \equiv 3$ serves only to place the element $9$ into the equivalence class containing $3$. If this relation is omitted from the list of relations in $(11)$, no chain of equivalences remains that can connect $9$ with any other element.
Therefore the transitive closure used to form the classes in $(12)$ changes in exactly one respect:
$$ [9]={9}, $$
while the class that formerly contained both $3$ and $9$ loses the element $9$.
All other classes remain unchanged, since none of the other identifications depend on the relation $9 \equiv 3$.
Hence the classes that appeared in $(12)$ are modified by replacing the class
$$ C\cup{9}, $$
where $C$ is the class containing $3$ obtained from the remaining relations, by the two classes
$$ C \qquad\text{and}\qquad {9}. $$
Thus $9$ becomes a singleton equivalence class, and every other equivalence class is exactly the same as before.
$$ \boxed{\text{Remove }9\text{ from the class containing }3,\text{ and add the new class }{9}.} $$