Isomorphic Graph Checker
Example Data Table
| Case | Graph Type | Vertices A/B | Graph A Edges | Graph B Edges | Expected Result |
|---|---|---|---|---|---|
| Path Example | Undirected | 4 / 4 | 1-2, 2-3, 3-4 | 1-4, 4-2, 2-3 | Isomorphic |
| Cycle vs Star | Undirected | 4 / 4 | 1-2, 2-3, 3-4, 4-1 | 1-2, 1-3, 1-4 | Not Isomorphic |
| Directed Pair | Directed | 3 / 3 | 1>2, 2>3 | 2>1, 1>3 | Isomorphic |
Formula Used
Graph isomorphism condition:
Two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic when there exists a bijection f: V₁ → V₂ such that an edge or arc between vertices in G₁ exists if and only if the corresponding mapped edge or arc exists in G₂.
- Undirected density: 2m / n(n−1)
- Directed density: m / n(n−1)
- Degree sequence: Sorted vertex degrees, or sorted (out-degree, in-degree) pairs for directed graphs.
- Fast invariants used: vertex count, edge count, loops, components, degree sequence, and triangle count for undirected graphs.
The checker first compares invariants, then runs a backtracking search for a vertex mapping that preserves adjacency. If a full mapping exists, the graphs are isomorphic.
How to Use This Calculator
- Choose whether your graphs are undirected or directed.
- Enter the total number of vertices for Graph A and Graph B.
- Type each edge list using numeric labels such as 1-2 or 1>2.
- Enable loops only when self-connections should be allowed.
- Adjust the search node limit if you want a deeper mapping search.
- Click Check Isomorphism to see the result above the form.
- Download the structured report with CSV or PDF buttons.
FAQs
1) What does graph isomorphic mean?
It means two graphs have the same structure after relabeling vertices. The names may differ, but the connection pattern stays identical.
2) Why can equal degree sequences still fail?
Degree sequences are necessary, not sufficient. Different graphs can share the same degrees while having different adjacency patterns, components, or triangle structures.
3) Does the tool support isolated vertices?
Yes. Isolated vertices are handled through the vertex count fields, even when they do not appear in the edge list.
4) Which edge formats are accepted?
Use 1-2 for undirected edges and 1>2 for directed arcs. Separate entries with commas, semicolons, or line breaks.
5) Can it check directed graphs too?
Yes. The checker compares in-degrees, out-degrees, and direction-preserving adjacency when directed mode is selected.
6) Why might the result say inconclusive?
That happens when invariants match but the search node limit stops the full mapping search before completion. Raising the limit may help.
7) Does it allow loops?
Yes, if you enable the loop option. Loop counts then become part of the invariant and mapping checks.
8) What does the reported mapping show?
It shows how each vertex in Graph A maps to a vertex in Graph B. That mapping preserves the connection pattern.