Question

Which of the following graphs are identical?

mr001-1.jpg

mr001-2.jpg

mr001-3.jpg

mr001-4.jpg

mr001-5.jpg

mr001-6.jpg

Answer 1

I can’t see the image files you listed. Please either upload the six pictures here or paste each graph’s description (vertex list + edge list, or adjacency matrix). Then I’ll determine which are identical (graph-isomorphic).

If you want to check them yourself, here are quick reliable methods (manual and programmatic):

Manual checklist (fast eliminations)
1. Compare basic invariants for each graph:
- number of vertices n
- number of edges m
- degree sequence (sorted list of vertex degrees)
- number of connected components
If any of these differ between two graphs, they are not identical (not isomorphic).

2. If basic invariants match, refine with more discriminating invariants:
- multiset of degrees of each vertex’s neighbors (for each vertex, sort its neighbors’ degrees; collect these multisets and compare across graphs)
- counts of triangles incident to each vertex (or global triangle count)
- list of cycle lengths (presence/absence of specific cycle lengths)
- eccentricity or distance-spectrum signatures (distance from a candidate root)
Differences in any of these rule out isomorphism.

3. If those all match, try to construct an explicit vertex mapping:
- pick a vertex in graph A with a unique signature (degree + neighbor-degree multiset) and map it to a vertex in graph B with the same signature
- iteratively map neighbors using the preserved adjacency conditions
- if you can map all vertices while preserving edges, graphs are isomorphic; if you reach a contradiction, try a different starting mapping or conclude not isomorphic.

Programmatic method (recommended for reliability)
- Use an existing graph-isomorphism routine. Example in Python with networkx:

from networkx import Graph
import networkx as nx

# build graphs G and H (example from edge lists)
G = Graph()
G.add_edges_from([(1,2),(2,3),(3,1), ...]) # replace with your edges
H = Graph()
H.add_edges_from([( 'a','b'),('b','c'),('c','a'), ...])

iso = nx.is_isomorphic(G, H)
print(iso) # True if identical up to relabeling

- For many graphs or for canonical labeling use tools like nauty/Traces or bliss for faster canonical forms.

If you upload the six images or paste their edges/lists, I’ll run through them and tell you which ones are identical, and show the explicit vertex mappings for any that are isomorphic.