1
$\begingroup$

I was told isomorphism was when two graphs are the same but have different forms. In order for it to be the same two vertices must be adjacent across the graphs. So if vertex1 is adjacent to vertex2 and vertex3 in one graph, than it must do so in the other. Also that isomorphism can easily be applied to other varietys of graphs.

The simple graphs $G1 = (V_1, E_1)$ and $G2 = (V_2, E_2)$ are isomorphic if there exists a one-to-one and onto function $f:V_1\to V_2$ with the property that $a$ and $b$ are adjacent in $G_1$ if and only if $f(a)$ and $f(b)$ are adjacent in $G_2$, for all $a$ and $b$ in $V_1$. Such a function $f$ is called an isomorphism. ∗ Two simple graphs that are not isomorphic are called nonisomorphic.

enter image description here

Are these two graphs isomorphic? They retain the same shape, but the direction of the edge from vertex1 to vertex4 changes between the two, so it cant be isomorphic, right? Well, I was told it was without an explanation. Are they wrong, or am I missing something? Any help would be appreciated.

$\endgroup$
1
$\begingroup$

In the original graph, vertices have following degrees.

$1$ — $2$ outs, $1$ in.

$2$ — $1$ out, $2$ ins.

$3$ — $2$ outs, $1$ in.

$4$ — $1$ out, $2$ ins.

Let's give the names to the vertices of the second graph: enter image description here

Here's their degrees:

$A$ — $1$ out, $2$ ins.

$B$ — $2$ outs, $1$ in.

$C$ — $2$ outs, $1$ in.

$D$ — $1$ out, $2$ ins.

Let's try to assign numbers to the letters. For vertex $A$, we have only two options: either $A$ is $2$ or $4$.

Suppose $A$ is $2$. Then $D$ can only be $4$ (can you see why?) and $C$ is $3$. Then $B$ is $1$, which it absolutely can be, since it has the same degree and is adjacent to the same vertices. By showing the isomorphism, we effectively prove its existence.


So the error was here:

They retain the same shape, but the direction of the edge from vertex1 to vertex4 changes between the two, so it cant be isomorphic

On the second graph, there are no named vertices, so you can't just say that the direction between some named vertices changed. You need to have a more rigorous method of proving that, and often the one I've described above will suffice.

$\endgroup$
  • $\begingroup$ I'm a fool, I can't believe I didn't see it this way first. I understand it now, I appreciate the help. $\endgroup$ – pudge Nov 10 '16 at 19:51

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.