Calculator
Enter the same vertex count for both graphs. Use one edge per line. Accepted formats include 1 2, 1-2, 1,2, or 1->2.
Example Data Table
| Example | Vertices | Graph A edges | Graph B edges | Expected result |
|---|---|---|---|---|
| Cycle with one diagonal | 4 | 1 2 2 3 3 4 4 1 1 3 |
1 2 2 3 3 4 4 1 2 4 |
Isomorphic |
| Path versus star | 5 | 1 2 2 3 3 4 4 5 |
1 2 1 3 1 4 1 5 |
Not isomorphic |
| Triangle versus chain | 3 | 1 2 2 3 3 1 |
1 2 2 3 |
Not isomorphic |
Formula Used
Two graphs are isomorphic when there exists a bijection between their vertex sets that preserves adjacency. In adjacency matrix form, the condition is:
Here, A₁ and A₂ are adjacency matrices, and P is a permutation matrix that reorders vertices. This calculator first compares structural invariants such as edge count, degree sequence, component sizes, loop count, and triangle count. If those checks pass, it performs a constrained backtracking search to find a valid vertex mapping.
How to Use This Calculator
- Enter labels for both graphs if you want custom names.
- Set the total number of vertices shared by both graphs.
- Choose directed or undirected mode.
- Select 1-based or 0-based vertex numbering to match your edge lists.
- Paste one edge per line for each graph.
- Enable screening mode for larger graphs when you only want fast invariant checks.
- Click the button to generate the result above the form.
- Review the mapping, matrix comparison, chart, and export options.
Frequently Asked Questions
1. What does this checker confirm?
It tests whether two graphs have the same structure after relabeling vertices. If a mapping exists that preserves every adjacency relation, the graphs are isomorphic.
2. Why do degree sequences matter?
Degree sequences are preserved under isomorphism. If two graphs have different degree sequences, they cannot be isomorphic, so the checker can reject them immediately.
3. Does matching invariants prove isomorphism?
No. Matching invariants only means the graphs remain candidates. A full mapping search is still needed because different graphs can share the same basic invariants.
4. Why is full search limited for larger graphs?
Exact checking may require testing many vertex permutations. That search can grow rapidly, so this page limits full mapping to practical sizes and offers fast screening mode.
5. Can I use directed graphs?
Yes. Directed mode preserves edge direction during every check. The calculator then compares in-degrees, out-degrees, and directed adjacency patterns before searching mappings.
6. What formats can I use for edges?
You can enter one edge per line with formats such as 1 2, 1-2, 1,2, or 1->2. The selected graph type controls how those pairs are interpreted.
7. What do the CSV and PDF exports include?
They include the main summary, graph statistics, invariant checks, candidate attempts, and any mapping that was found during the exact search.
8. What does the chart show?
The Plotly chart compares vertex degree values across both graphs. It gives a quick visual check before you inspect the detailed invariant table and mapping.