IsomorphicGraphQ

IsomorphicGraphQ[g1,g2]

yields True if the graphs g1 and g2 are isomorphic, and False otherwise.

Details

  • Two graphs are isomorphic if there is a renaming of vertices that makes them equal.
  • IsomorphicGraphQ[g1,g2,] gives True if all the gi are isomorphic.

Examples

open allclose 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:

Scope  (4)

IsomorphicGraphQ works with undirected graphs:

Directed graphs:

IsomorphicGraphQ gives False for non-isomorphic graphs:

As well as non-graph expressions:

IsomorphicGraphQ works with 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:

Introduced in 2010
 (8.0)
 |
Updated in 2012
 (9.0)