# Graph Isomorphism

A graph isomorphism is a bijective function on two graphs (with graph edges $\displaystyle{ E_1, E_2 }$) such that if $\displaystyle{ \{e_i,e_j\}\in E_1 }$ then also $\displaystyle{ \{e_i,e_j\}\in E_2 }$.

## References

### 2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/graph_isomorphism Retrieved:2015-11-16.
• In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H : $\displaystyle{ f \colon V(G) \to V(H) \,\! }$ such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is generally called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.

If an isomorphism exists between two graphs, then the graphs are called isomorphic and we write $\displaystyle{ G\simeq H }$ . In the case when the bijection is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the bijection is called an automorphism of G.

A graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs.

The two graphs shown below are isomorphic, despite their different looking drawings.

Graph G Graph H An isomorphism
between G and H
File:Graph isomorphism a.svg File:Graph isomorphism b.svg f(a) = 1

f(b) = 6

f(c) = 8

f(d) = 3

f(g) = 5

f(h) = 2

f(i) = 4

f(j) = 7