Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

They meet the requirements of both having an $=$ number of vertices ($7$).

They both have the same number of edges ($9$).

They both have $3$ vertices of degree $2$ and $4$ of degree $3$.

However, graph two has $2$ simple circuits of length $3$ whereas graph one has only $1$ of length $3$.

Is this not a valid method for checking isomorphism?

My guide says that these two figures are isomorphic.

share|improve this question
6  
It's a valid method, but I see only one 3-cycle in the second graph. I would look for an isomorphism, if I were you. –  Gerry Myerson May 16 '13 at 11:06
    
Aren't both 1-5-6 and 5-4-7 simple circuits of length 3? And what do you mean by your second statement? –  Kevin Duke May 16 '13 at 11:13
2  
@KevinDuke There is no edge between vertices 5 and 7. I agree with Gerry that they appear to be isomorphic, and that the easiest way to show this is to write down an isomorphism. –  Matt Pressland May 16 '13 at 12:25
    
I see, 5 is not an edge with 7. I guess that was my mental block. What do you mean however to "write down an isomorphism"? –  Kevin Duke May 16 '13 at 12:26
    
@KevinDuke Write it down, as in, identify which vertexes correspond and so on. Node 6 corresponds to D and so on. Then write an adjacency matrix for the nodes of both graphs, where the nodes are in the same order, and compare. –  Kaz May 16 '13 at 15:57

4 Answers 4

up vote 64 down vote accepted

Once you have an isomorphism, you can create an animation illustrating how to morph one graph into the other. Let's say that ${vc}_1$ is a list of vertex coordinates for one and ${vc}_2$ is the corresponding list of vertex coordinates for the other. (It's important that the order of the vertex coordinates be dictated by the isomorphism.) We can then morph from one graph to the other using a function like

$$p(t) = t \, {vc}_2 + (1-t) {vc}_1.$$

Here's the result.

enter image description here

Code

The movie can be generated using the following Mathematica code.

vc1 = # - {1, 1} & /@ {{0, 2}, {1, 2}, {2, 2}, {1, 1}, 
  {0, 0}, {1, 0}, {2, 0}};
vc2 = {{1/2, -Sqrt[3]/2}, {-1/2, -Sqrt[3]/2}, {-1, 0}, 
  {1/2, Sqrt[3]/2}, {1, 0}, {0, 0}, {-1/2, Sqrt[3]/2}};
vc[t_] := t*vc2 + (1 - t) vc1;
Animate[
  Graph[{1, 2, 3, 4, 5, 6, 7},
    UndirectedEdge@@@{{1, 2}, {2, 3}, {3, 7}, {7, 6}, {6, 5}, {5, 1}, 
     {1, 6}, {4, 5}, {4, 7}},
    PlotRange -> 1.1, VertexCoordinates -> vc[t]],
  {t, 0, 1}, AnimationDirection -> ForwardBackward]
share|improve this answer
8  
How did you make this movie? –  John Smith May 16 '13 at 13:25
6  
@JohnSmith I used Mathematica. I've added commentary to describe the basic idea. I could post the code if there's interest. –  Mark McClure May 16 '13 at 13:47
5  
I would be interested in seeing the code, if you don't mind. –  Chase Meadors May 16 '13 at 21:13
5  
There is interest. –  Carter Pape May 17 '13 at 0:37
2  
o my god..... beautiful explanation wid moving diagram.... hats off to you @MarkMcClure –  monalisa May 17 '13 at 9:45

There's an isomorphism $f$ given on vertices by

$$f(A)=7,\: f(B)=4,\: f(C)=3,\: f(D)=6,\: f(E)=5,\: f(F)=2,\: f(G)=1.$$

An illustration of the isomorphism is given below:

An illustration of the isomorphism

share|improve this answer
11  
I added an illustration of the isomorphism; hope you don't mind. –  Douglas S. Stones May 16 '13 at 13:08
1  
That's very kind of you. Thanks. –  Daniel Rust May 16 '13 at 13:32

If two graphs are isomorphic, then if we represent one of them as an matrix, we can find an adjacency matrix for the other which is identical, except for the names of the nodes and edges.

An adjacency matrix for the left graph is:

   A B C D E F G
A:   1 1 1       
B: 1     1 1
C: 1         1
D: 1       1   1
E:   1   1     1
F:     1       1
G:       1 1 1

If we identify the vertices as (A B C D E F G) = (7 4 3 6 5 2 1), and write down the adjacency matrix for the second graph in that order, we get the same matrix:

   7 4 3 6 5 2 1
7:   1 1 1       
4: 1     1 1
3: 1         1
6: 1       1   1
5:   1   1     1
2:     1       1
1:       1 1 1

Of course, the objects are not isomorphic if the names of the vertices are considered significant in the representation. Or if there are constraints, such as that A must be identified with node 1 (because, say, the graph are part of some larger object, and how they connect to it is not negotiable).

Two entities that are considered isomorphic are never identical unless they are the same entity.

An isomorphism is always based on caring about some possible differences, while declaring that others do not matter.

share|improve this answer

Yes. In the second graph, slide node 4 out of the square and observe that nodes 1,2,3,7,4,5 now form a hexagon, with node 6 inside it. Node 6 now corresponds to node D. For rigorous details, see Daniel Rust's answer. You can check that his construction is indeed an isomorphism by applying the definition: that for any $a$, $b$ in the first graph, $f(a)$ is connected to $f(b)$ if and only if $a$ is connected to $b$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.