Graph Isomorphism

•Two graphs G=(V,E) and H=(W,F) are isomorphic if there is a bijective function f: V ® W such that for all v, w Î V:

–{v,w} Î E Û {f(v),f(w)} Î F

Variant for labeled graphs

•Let G = (V,E), H=(W,F) be graphs with vertex labelings l: V ® L, l’ ® L.

•G and H are isomorphic labeled graphs, if there is a bijective function f: V ® W such that

–For all v, w Î V: {v,w} Î E Û {f(v),f(w)} Î F

–For all v Î V: l(v) = l’(f(v)).

•Application: organic chemistry:

–determining if two molecules are identical.

Complexity of graph isomorphism

•Problem is in NP, but

–No NP-completeness proof is known

–No polynomial time algorithm is known

•Problems are isomorphism-

complete, if they are `equally 

hard’ as graph isomorphism

–Isomorphism of bipartite graphs

–Isomorphism of labeled graphs

–Automorphism of graphs

•Given: a graph G=(V,E)

•Question: is there a non-trivial 

automorphism, i.e., a bijective

 function f: V ® V, not the identity,

 with for all v,wÎV:

–{v,w} Î E, if and only if 

{f(v),f(w)} Î E.