GraphLab

Graph theory & algorithm visualizer
About Graph isomorphism

GraphLab › Graph isomorphism

Graph Isomorphism Checker: Are Two Graphs the Same?

Two graphs are isomorphic when they have the same structure: you can rename the vertices of one to get exactly the other. They may look completely different on paper.

How to check

First compare properties that isomorphic graphs must share, called invariants:

  1. Number of vertices and number of edges.
  2. Degree of each vertex (the degree sequence).
  3. Number of connected components.
  4. Number and length of cycles.

If any invariant differs, the graphs are not isomorphic. If they all match, look for a matching of the vertices that keeps every edge.

Try it in GraphLab

The drawing area is split in two: vertices on the left form G₁ and vertices on the right form G₂. Drag vertices across the middle line to change which graph they belong to.

More topics