Graph isomorphism

A graph isomorphism is a bijection (a one-to-one and onto mapping) between the vertices of two graphs G and H

$f: V(G) \rightarrow V(H)$

with the property that any two vertices u and v from G are adjacent if and only if f(u) and f(v) are adjacent in H.

If an isomorphism can be constructed between two graphs, then we say those graphs are isomorphic.

Determining whether two graphs are isomorphic is referred to as the graph isomorphism problem.

[edit] Example

Graph G	Graph H	An isomorphism between G and H
		$f (a) = 1$ $f (b) = 6$ $f (c) = 8$ $f (d) = 3$ $f (g) = 5$ $f (h) = 2$ $f (i) = 4$ $f (j) = 7$

This article incorporates material from graph isomorphism on PlanetMath, which is licensed under the GFDL.