28
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson May 16 '13 at 11:06
  • $\begingroup$ Aren't both 1-5-6 and 5-4-7 simple circuits of length 3? And what do you mean by your second statement? $\endgroup$ – dukevin May 16 '13 at 11:13
  • 2
    $\begingroup$ @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. $\endgroup$ – mdp May 16 '13 at 12:25
  • $\begingroup$ 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"? $\endgroup$ – dukevin May 16 '13 at 12:26
  • $\begingroup$ @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. $\endgroup$ – Kaz May 16 '13 at 15:57
77
$\begingroup$

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]
$\endgroup$
  • 9
    $\begingroup$ How did you make this movie? $\endgroup$ – John Smith May 16 '13 at 13:25
  • 7
    $\begingroup$ @JohnSmith I used Mathematica. I've added commentary to describe the basic idea. I could post the code if there's interest. $\endgroup$ – Mark McClure May 16 '13 at 13:47
  • 5
    $\begingroup$ I would be interested in seeing the code, if you don't mind. $\endgroup$ – cemulate May 16 '13 at 21:13
  • 5
    $\begingroup$ There is interest. $\endgroup$ – Carter Pape May 17 '13 at 0:37
  • 2
    $\begingroup$ o my god..... beautiful explanation wid moving diagram.... hats off to you @MarkMcClure $\endgroup$ – monalisa May 17 '13 at 9:45
22
$\begingroup$

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

$\endgroup$
  • 12
    $\begingroup$ I added an illustration of the isomorphism; hope you don't mind. $\endgroup$ – Douglas S. Stones May 16 '13 at 13:08
  • 2
    $\begingroup$ That's very kind of you. Thanks. $\endgroup$ – Dan Rust May 16 '13 at 13:32
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ After four years, can you tell me how did you figure out this part: "If we identify the vertices as (A B C D E F G) = (7 4 3 6 5 2 1)," ? Is it experience or is it something else? $\endgroup$ – user481197 Dec 12 '17 at 6:47
5
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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