Theorem: Isomorphism is Equivalence Relation

Isomorphism is an equivalence on a set of magmas.
This result applies to all magmas: rings, groups, R-algebraic structures etc.

Proof:
In the following, let:
{{begin-eqn}}
{{eqn | l = G_1
      | r = \struct {\map V {G_1}, \map E {G_1} }
}}
{{eqn | l = G_2
      | r = \struct {\map V {G_2}, \map E {G_2} }
}}
{{eqn | l = G_3
      | r = \struct {\map V {G_3}, \map E {G_3} }
}}
{{end-eqn}}
be arbitrary graphs.
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
The identity mapping on $\map V {G_1}$ is a bijection that maps each vertex to itself.
This is seen to preserve adjacency.
Thus graph isomorphism preserves reflexivity.
{{qed|lemma}}
=== Symmetry ===
Let $G_1$ be isomorphic to $G_2$
Then there exists an isomorphism $\phi: \map V {G_1} \to \map V {G_2}$ from $\map V {G_1}$ to $\map V {G_2}$.
Let its inverse $\phi^{-1}: \map V {G_2} \to \map V {G_1}$ be defined by:
:$\map {\phi^{-1} } {v_2} = v_1 \iff \map \phi {v_1} = v_2$
By Inverse of Bijection is Bijection, $\phi^{-1}$ is a bijection.
Let $u_2, v_2 \in \map V {G_2}$ such that $\map {\phi^{-1} } {u_2} = u_1$ and $\map {\phi^{-1} } {v_2} = v_1$.
Then:
{{begin-eqn}}
{{eqn | l = \map \phi {u_1}
      | r = u_2
}}
{{eqn | l = \map \phi {v_1}
      | r = v_2
}}
{{end-eqn}}
So $u_2$ and $v_2$ are adjacent {{iff}} $\map \phi {u_1}$ and $\map \phi {v_1}$ are adjacent.
Because $G_1$ is isomorphic to $G_2$, $\map \phi {u_1}$ and $\map \phi {v_1}$ are adjacent {{iff}} $u_1 = \map {\phi^{-1} } {u_2}$ and $v_1 = \map {\phi^{-1} } {v_2}$ are adjacent.
So $u_2$ and $v_2$ are adjacent {{iff}} $u_1 = \map {\phi^{-1} } {u_2}$ and $v_1 = \map {\phi^{-1} } {v_2}$ are adjacent.
That is, $G_2$ is isomorphic to $G_1$
Thus graph isomorphism preserves symmetry.
{{qed|lemma}}
=== Transitivity ===
Let $G_1$ be isomorphic to $G_2$ and $G_2$ be isomorphic to $G_3$.
Then there exist isomorphisms:
:$\alpha: \map V {G_1} \to \map V {G_2}$ from $\map V {G_1}$ to $\map V {G_2}$
:$\beta: \map V {G_2} \to \map V {G_3}$ from $\map V {G_2}$ to $\map V {G_3}$.
Consider the composite mapping $\beta \circ \alpha$.
From Composite of Bijections is Bijection, $\beta \circ \alpha$ is a bijection from $\map V {G_1}$ to $\map V {G_3}$.
Let $u_1, v_1 \in \map V {G_1}$.
Let $\map \alpha {u_1} = u_2$ and $\map \alpha {v_1} = v_2$.
Let $\map \beta {u_2} = u_3$ and $\map \beta {v_2} = v_3$.
We have that $\alpha$ and $\beta$ are isomorphisms.
So:
:$u_1$ and $v_1$ are adjacent {{iff}} $\map \alpha {u_1} = u_2$ and $\map \alpha {v_1} = v_2$ are adjacent
:$u_2$ and $v_2$ are adjacent {{iff}} $\map \beta {u_2} = u_3$ and $\map \beta {v_2} = v_3$ are adjacent.
Thus:
:$u_1$ and $v_1$ are adjacent {{iff}} $\map \beta {\map \alpha {u_1} } = u_3$ and $\map \beta {\map \alpha {v_1} } = v_3$ are adjacent.
That is, {{iff}} $\map {\paren {\beta \circ \alpha} } {u_1} = u_3$ and $\map {\paren {\beta \circ \alpha} } {v_1} = v_3$ are adjacent.
Thus it has been demonstrated that $\beta \circ \alpha$ is an isomorphism.
Thus graph isomorphism has been shown to preserve transitivity.
{{qed|lemma}}
Graph isomorphism has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
{{qed}}