IsIsomorphicGraph

Whether two Graph values have the same structure, up to relabelling vertices.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageIsomorphicGraphQ✓↗

IsIsomorphicGraph(g1, g2)true iff some relabelling of g1's vertices reproduces g2's edges exactly (direction included); unevaluated once either graph has more than 9 vertices.

Typed signatures

Type	Package	Applies
(value, value) -> boolean	combinatorics	always

Domain: Collections

Details

• Wolfram calls this IsomorphicGraphQ; this library uses the Is… spelling everywhere.
• Brute force over all n! vertex permutations, cheap-filtered first by vertex count, edge count and sorted degree sequence -- fine through 9 vertices (9! = 362,880), unevaluated beyond that rather than guessing.

Examples

Basic #

live ↗

In$\mathrm{IsIsomorphicGraph}(\mathrm{CycleGraph}(4), \mathrm{Graph}(\bigl\lbrack3, 1, 4, 2\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(3, 1), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(4, 2), \mathrm{UndirectedEdge}(2, 3)\bigr\rbrack))$Out$\mathrm{True}$

live ↗

In$\mathrm{IsIsomorphicGraph}(\mathrm{CycleGraph}(4), \mathrm{StarGraph}(4))$Out$\mathrm{False}$

Scope #

Cycles of different lengths have different vertex counts

live ↗

In$\mathrm{IsIsomorphicGraph}(\mathrm{CycleGraph}(3), \mathrm{CycleGraph}(4))$Out$\mathrm{False}$

About

Examples	3
Checked against	Wolfram Language 3 agreeSageMath 3 agree
Crosswalk	Wolfram Language

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: IsConnectedGraph