# Graph Isomorphism is Equivalence Relation

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 $E$ on $V$.

### Digraph

A digraph $D$ is a non-empty set $V$ together with an antireflexive relation $E$ on $V$.

### Loop-graph

A loop-graph $P$ is a non-empty set $V$ together with a symmetric relation $E$ on $V$.

### Loop-Digraph

A loop-digraph $D$ is a non-empty set $V$ together with a relation $E$ 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$

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): $\S 2.2$: Isomorphic Graphs: Theorem $2.3$