Graph Isomorphism is Equivalence Relation/Proof 1
Jump to navigation
Jump to search
Theorem
Graph isomorphism is an equivalence relation.
Proof
From the formal definitions:
Simple Graph
A (simple) graph $G$ is a non-empty set $V$ together with an antireflexive, symmetric relation $\RR$ on $V$.
Digraph
A digraph $D$ is a non-empty set $V$ together with an antireflexive relation $\RR$ on $V$.
Loop-graph
A loop-graph $P$ is a non-empty set $V$ together with a symmetric relation $\RR$ on $V$.
Loop-Digraph
A loop-digraph $D$ is a non-empty set $V$ together with a relation $\RR$ on $V$.
It can be seen from these definitions that all the above are relational structures with more or less restriction on the relation.
Hence the result from Relation Isomorphism is Equivalence Relation.
$\blacksquare$