({{, (RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism])[(Subscript[g, 1]),(Subscript[g, 2])] 
finds an isomorphism that maps the graph (Subscript[g, 1]) to (Subscript[g, 2]) by renaming vertices.}, {, (RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism])[(Subscript[g, 1]),(Subscript[g, 2]),n]
finds at most n isomorphisms. }, {, (RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism])[{v->w,…},…]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details and Options

(RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism]) gives a list of associations (RefLink[Association, paclet:ref/Association])[(Subscript[v, 1])->(Subscript[w, 1]),(Subscript[v, 2])->(Subscript[w, 2]),…] where (Subscript[v, i]) are vertices in (Subscript[g, 1]) and (Subscript[w, i]) are vertices in (Subscript[g, 2]).

(RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism]) gives an empty list if no isomorphism can be found.

(RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism])[(Subscript[g, 1]),(Subscript[g, 2]),(RefLink[All, paclet:ref/All])] gives all the isomorphisms.

Two graphs are isomorphic if there is a renaming of vertices that makes them equal.

OpenersPrimaryExamplesSection(Spacer1)Examples  (14)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Find an isomorphism that maps two graphs:

FindGraphIsomorphism[,]

Find all isomorphisms:

FindGraphIsomorphism[,,All]

OpenersExampleSection1(Spacer1)Scope  (8)

OpenersExampleSubsection0(Spacer1)Specification  (5)

(RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism]) works with undirected graphs:

FindGraphIsomorphism[,]

Directed graphs:

FindGraphIsomorphism[,]

Use rules to specify the graph:

FindGraphIsomorphism[{1->2,1->3,1->4},{"a"->"b","a"->"c","a"->"d"}]

It returns an empty list if no isomorphism can be found:

FindGraphIsomorphism[CycleGraph[3],CycleGraph[4]]

(RefLink[FindGraphIsomorphism, paclet:ref/FindGraphIsomorphism]) works with large graphs:

g=GridGraph[{10,10,10}];

h=VertexReplace[g,Thread[VertexList[g]->RandomSample[VertexList[g],VertexCount[g]]]];

FindGraphIsomorphism[g,h]//Short//Timing

OpenersExampleSubsection1(Spacer1)Enumeration  (3)

Find an isomorphism that maps two graphs:

FindGraphIsomorphism[,]

Find at most two isomorphisms:

FindGraphIsomorphism[,,2]

Find all isomorphisms:

FindGraphIsomorphism[,,All]

OpenersExampleSection3(Spacer1)Applications  (1)

Find an isomorphism that maps two graphs:

g=PetersenGraph[4,1,VertexLabels->"Name",ImagePadding->10,VertexSize->Large];

v1={"a","b","c","d"};v2={"e","f","g","h"};

edge=Table[(v1[[i]]\[UndirectedEdge]#)&/@Delete[v2,5-i],{i,4}]//Flatten;

h=Graph[Join[v1,v2],edge,VertexLabels->"Name",ImagePadding->10,VertexSize->Large,AbsoluteOptions[CompleteGraph[{4,4}],VertexCoordinates]];

map=(Normal/@FindGraphIsomorphism[g,h])[[1]]

Highlight and label two graphs according to the mapping:

a=First/@map;b=Last/@map;

highlightGraph[g_,v_]:=HighlightGraph[g,Table[Style[Labeled[v[[i]],v[[i]]],ColorData["TemperatureMap"][i/VertexCount[g]]],{i,VertexCount[g]}]];

{highlightGraph[g,a],highlightGraph[h,b]}

OpenersExampleSection4(Spacer1)Properties & Relations  (3)

Isomorphic graphs have the same number of vertices and edges:

{g,h}={PetersenGraph[4,1],HypercubeGraph[3]}

FindGraphIsomorphism[g,h]

VertexCount[g]==VertexCount[h]

EdgeCount[g]==EdgeCount[h]

Test whether two graphs are isomorphic using (RefLink[IsomorphicGraphQ, paclet:ref/IsomorphicGraphQ]):

{g,h}={CycleGraph[4],Graph[{2\[UndirectedEdge]3,3\[UndirectedEdge]4,4\[UndirectedEdge]1,1\[UndirectedEdge]2}]}

FindGraphIsomorphism[g,h]

IsomorphicGraphQ[g,h]

Isomorphic graphs have the same canonical graph:

g=;h=;

FindGraphIsomorphism[g,h]

CanonicalGraph[h]==CanonicalGraph[g]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[IsomorphicGraphQ, paclet:ref/IsomorphicGraphQ])  ▪  (RefLink[CanonicalGraph, paclet:ref/CanonicalGraph])  ▪  (RefLink[GraphAutomorphismGroup, paclet:ref/GraphAutomorphismGroup])  ▪  (RefLink[VertexReplace, paclet:ref/VertexReplace])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Properties & Measurements, paclet:guide/GraphPropertiesAndMeasurements])}, {▪(RefLinkPlain[Graph Predicates and Properties, paclet:guide/GraphPredicates])}, {▪(RefLinkPlain[Discrete Mathematics, paclet:guide/DiscreteMathematics])}})}})