BUILT-IN MATHEMATICA SYMBOL

IsomorphicGraphQ

yields True if the graphs

and

are isomorphic, and False otherwise.

MORE INFORMATION

IsomorphicGraphQ works for any graph object including Graph, DirectedGraph, TreeGraph, etc.

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

EXAMPLES

CLOSE ALL

Basic Examples (1)

Test whether two graphs are isomorphic:

Find an isomorphism that maps g to h:

Renaming the vertices of graph g gets an equal graph as h:

Test whether two graphs are isomorphic:

In[1]:=

In[2]:=

Out[2]=

Find an isomorphism that maps g to h:

In[3]:=

Out[3]=

Renaming the vertices of graph g gets an equal graph as h:

In[4]:=

Out[4]=

Scope (4)

Test undirected graphs:

Test directed graphs:

IsomorphicGraphQ gives False for non-isomorphic graphs:

As well as non-graph expressions:

Test large graphs:

Properties & Relations (10)

Isomorphic graphs have the same number of vertices and edges:

The isomorphic graphs have the same ordered degree sequence:

The graphs with the same degree sequence can be non-isomorphic:

FindGraphIsomorphism can be used to find the mapping between vertices:

Highlight and label two graphs according to the mapping:

Permuting the vertices in a graph produces an isomorphic graph:

The graph generated by the permutation of its adjacency matrix is isomorphic to itself:

Sample a permutation of the vertex list:

The line graph of a cycle graph

is isomorphic to

itself:

The line graph of a path

is isomorphic to

:

The complement of the line graph of

is isomorphic to a Petersen graph:

Two connected graphs are isomorphic iff their line graphs are isomorphic:

With one exception:

The non-isomorphic directed graphs can have undirected graphs that are isomorphic: