yields True if the graphs g1 and g2 are isomorphic, and False otherwise.
- IsomorphicGraphQ is also known as graph isomorphism problem.
- IsomorphicGraphQ is typically used to determine whether two graphs are structurally equivalent.
- 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.
Examplesopen allclose all
Basic Examples (1)
IsomorphicGraphQ works with undirected 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:
The non-isomorphic directed graphs can have undirected graphs that are isomorphic:
Wolfram Research (2010), IsomorphicGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html (updated 2012).
Wolfram Language. 2010. "IsomorphicGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2012. https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html.
Wolfram Language. (2010). IsomorphicGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html