# Checking graph isormorphism in Matgraph

We show how to determine if two graphs are isomorphic and, if so, how to find the permutation that transforms one into the other.

## Contents

## Cycle graph

Create two copies of a cycle on 10 vertices, but randomly renumber the second.

g = graph; h = graph; cycle(g,10); cycle(h,10); renumber(h,random(permutation(nv(h)))); figure(1); clf; ndraw(g); figure(2); clf; ndraw(h); [yn,p] = iso(g,h) renumber(g,p) if g==h disp('Graphs are the same') else disp('Graphs are different') end

yn = 1 (1)(2,9,4,3,7,5)(6)(8,10) Graphs are the same

## Large, vertex regular graph

The bucky graph is a vertex transitive graph with 60 vertices. We make two copies (one that is randomly renumbered) and check they are the same.

bucky(g); bucky(h); renumber(h,random(permutation(nv(h)))); [yn,p] = iso(g,h) renumber(g,p) if g==h disp('Graphs are the same') else disp('Graphs are different') end

yn = 1 (1)(2,28,6,55,16,24,27,45,8,21,13,43,54,19,12,35,49,56,4,32,52,57,47,51,60,15,3,30,11,41,10,33,59,58,53,40,37,44)(5,34,39,42,9,46,38,18)(7,14,25,36,23,20,29)(17,31)(22,48)(26)(50) Graphs are the same

## Standard random graph

We generate a standard Erdos-Renyi random graph and a randomly renumbered copy, and then verify they are isomorphic.

random(g,100,0.5) copy(h,g) renumber(h,random(permutation(nv(h)))); [yn,p] = iso(g,h); renumber(g,p) if g==h disp('Graphs are the same') else disp('Graphs are different') end

Graphs are the same

## Random regular graph

We generate a random 3-regular graph and a randomly renumbered copy, and then verify they are isomorphic.

random_regular(g,100,3); copy(h,g); renumber(h,random(permutation(nv(h)))); [yn,p] = iso(g,h); renumber(g,p) if g==h disp('Graphs are the same') else disp('Graphs are different') end

Graphs are the same

## Random tree

We generate a random tree and a randomly renumbered copy, and then verify they are isomorphic.

random_tree(g,100); copy(h,g); renumber(h,random(permutation(nv(h)))); [yn,p] = iso(g,h); renumber(g,p) if g==h disp('Graphs are the same') else disp('Graphs are different') end

Graphs are the same

## Two ways to make a grid

We generate a grid graph in two different ways. The graphs are not equal, but they are isomorphic.

grid(g,6,3); grid(h,3,6); if g==h disp('Graphs are the same') else disp('Graphs are different') end [yn,p] = iso(g,h) renumber(g,p) if g==h disp('Graphs are the same') else disp('Graphs are different') end

Graphs are different yn = 1 (1)(2,4,10,11,14,6,16,12,17,15,9,8,5,13,3,7)(18) Graphs are the same

## Mobius and non-Mobius ladders are not isomorphic

The Mobius ladder on 20 vertices and the Cartesian product of a 10-cycle and an edge are both 3-regular graphs on 20 vertices. But they are not isomorphic.

mobius(g,20); c10 = graph; cycle(c10,10); k2 = graph; add(k2,1,2); cartesian(h,c10,k2); figure(1); clf; draw(g); distxy(h); figure(2); clf; draw(h); [yn,p] = iso(g,h) if yn disp('Graphs are isomorphic') else disp('Graphs are not isomorphic') end

Optimization terminated: relative function value changing by less than OPTIONS.TolFun. Embedding score = 20.7351 Elapsed time is 2.634896 seconds. yn = 0 () Graphs are not isomorphic

## Release storage

free(g); free(h); free(c10); free(k2);