31
$\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$
5
  • 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$ May 16, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 15:57

4 Answers 4

83
$\begingroup$

Once you know, as pointed out in this answer, that $$f(A)=7,\: f(B)=4,\: f(C)=3,\: f(D)=6,\: f(E)=5,\: f(F)=2,\: f(G)=1$$ 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

Since several folks asked for code generating the animation in the comments, you can find it here:

$\endgroup$
8
  • 10
    $\begingroup$ How did you make this movie? $\endgroup$
    – John Smith
    May 16, 2013 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$ May 16, 2013 at 13:47
  • 5
    $\begingroup$ I would be interested in seeing the code, if you don't mind. $\endgroup$
    – cemulate
    May 16, 2013 at 21:13
  • 6
    $\begingroup$ There is interest. $\endgroup$ May 17, 2013 at 0:37
  • 2
    $\begingroup$ o my god..... beautiful explanation wid moving diagram.... hats off to you @MarkMcClure $\endgroup$
    – monalisa
    May 17, 2013 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$
2
  • 12
    $\begingroup$ I added an illustration of the isomorphism; hope you don't mind. $\endgroup$ May 16, 2013 at 13:08
  • 2
    $\begingroup$ That's very kind of you. Thanks. $\endgroup$
    – Dan Rust
    May 16, 2013 at 13:32
20
$\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$
1
  • $\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, 2017 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.