View source for Graph isomorphism

An equivalence relation on the set of graphs. An isomorphic mapping of a non-oriented graph to another one is a one-to-one mapping of the vertices and the edges of one graph onto the vertices and the edges, respectively, of the other, the incidence relation being preserved. Two graphs are said to be isomorphic if there exists an isomorphic mapping of one of these graphs to the other. In the figure, the graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449501.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449502.png" /> are not isomorphic, whereas the graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449503.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449504.png" /> are isomorphic. Isomorphic graphs are usually not distinguished from one another. The number of pairwise non-isomorphic graphs with a given number of vertices and a given number of edges is finite. Isomorphism of oriented graphs, hypergraphs and networks can be defined in a similar manner.

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044950a.gif" />

Figure: g044950a

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044950b.gif" />

Figure: g044950b

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044950c.gif" />

Figure: g044950c

The problem of establishing an isomorphism between graphs is an important problem in graph theory. There are algorithms for certain classes of graphs with the aid of which isomorphism can be fairly effectively recognized (e.g. for trees, cf. [[Tree|Tree]], or planar graphs, [[#References|[1]]]). Certain classes of graphs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449505.png" /> vertices have been proved to be uniquely reconstructible (up to an isomorphism) from the set of subgraphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449506.png" /> of it with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449507.png" /> vertices obtained by removing the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449508.png" /> in all possible ways. This has been established, in particular, for trees and tournaments (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g0449509.png" />, cf. [[Tournament|Tournament]])

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J.E. Hopcroft,   R.E. Tarjan,   "Isomorphism of planar graphs"  R.E. Miller (ed.)  J.W. Tatcher (ed.) , ''Complexity of Computer Computations. Proc. Symp. IBM'' , Plenum  (1972)  pp. 131–152; 187–212</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.J. Kelly,   "A congruence theorem for trees"  ''Pacific J. Math.'' , '''7'''  (1957)  pp. 961–968</TD></TR></table>



====Comments====
The graph isomorphism problem in general belongs to the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g04495010.png" /> but has not been proved to be in the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g04495011.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044950/g04495012.png" /> and is of great interest in the study of computational complexity. See the surveys [[#References|[a1]]] and [[#References|[a2]]] and also [[Complexity theory|Complexity theory]].

The reconstruction problem is usually called the Kelly–Ulam reconstruction conjecture. The earliest reference is in [[#References|[a3]]]. Many classes of graphs have since been proved to be reconstructible. For recent surveys see [[#References|[a4]]] and [[#References|[a5]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.C. Read,   D.G. Corneil,   "The graph isomorphism disease"  ''J. Graph Theory'' , '''1'''  (1977)  pp. 339–363</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Gati,   "Further annotated bibliography on the isomorphism disease"  ''J. Graph Theory'' , '''3'''  (1979)  pp. 95–109</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S.M. Ulam,   "A collection of mathematical problems" , Wiley  (1960)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J.A. Bondy,   R.L. Hemminger,   "Graph reconstruction—a survey"  ''J. Graph Theory'' , '''1'''  (1977)  pp. 227–268</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  C.St.J.A. Nash-Williams,   "The reconstruction problem"  L.W. Beineke (ed.)  R.J. Wilson (ed.) , ''Selected Topics in Graph Theory'' , Acad. Press  (1978)  pp. Chapt. 8</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J.E. Hopcroft,   R.E. Tarjan,   "Isomorphism of planar graphs"  R.E. Miller (ed.)  J.W. Tatcher (ed.) , ''Complexity of Computer Computations. Proc. Symp. IBM'' , Plenum  (1972)  pp. 131–152; 187–212</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.E. Hopcroft,   R.E. Tarjan,   "Efficient planarity testing"  ''J. ACM'' , '''21'''  (1974)  pp. 549–568</TD></TR></table>