Are these two graphs isomorphic?

Question

I have the attached the images of two graphs. I want to know whether two graphs are planar or not. ? I also want to know whether two graphs are planar or not ? enter image description here

What are your thoughts on this? Can you tell whether $G_2$ is planar, for example? — hmakholm left over Monica, Feb 24 '14 at 15:58
G2 on the other hand is planar as discussed in various papers of spider web networks ... G1 is an isomorph of G2..as the vertices of the graph G1 holds a bijective relation with the vertices of graph G2. But can be G1 be a planar graph ? — Raju Parashar, Feb 24 '14 at 18:45
x @Raju: That's overcomplicating it. $G_2$ is planar because you're currently looking at a plane drawing of it! — hmakholm left over Monica, Feb 24 '14 at 18:47
but two isomorphic graphs represent same properties..then from that respect can we say that G1 is also planar..? — Raju Parashar, Feb 24 '14 at 19:06

score 3 · Answer 1 · answered Feb 24 '14 at 16:02

3

Hint: #1 looks like a three-dimensional structure (two cubes stacked one atop the other). What would you see if you looked at them from above?

answered Feb 24 '14 at 16:02

Robert Israel

448,999

$\phantom{AAAA}$A square? – Pp.. Jan 26 '15 at 03:14

Sergio Da Silva · Accepted Answer · 2014-02-24T16:08:43.207

1

The two graphs are indeed isomorphic. Simply take $G_1$, and "collapse" it down to $G_2$. More specifically, map the upper 4 vertices (upper row) of $G_1$ to the inner square of $G_2$, the middle row to the middle square, and the lower row to the outer square (Do so in the obvious way so that edge pairings are preserved).

$G_2$ is planar, so both are in fact planar.

edited Feb 24 '14 at 16:08

answered Feb 24 '14 at 16:03

Sergio Da Silva

1,970

but can we draw the 3-dimesional cube structured graph in a single plane without any edge crossover ? – Raju Parashar Feb 24 '14 at 18:40
Being planar is preserved under an isomorphism, so yes, $G_1$ can be drawn as a planar graph, and $G_2$ is this graph. – Sergio Da Silva Feb 24 '14 at 20:50
If you are still having trouble seeing this, picture $G_1$ as balls attached by strings (for the vertices and edges). The graph $G_1$ is you holding up the top square (letting the rest hang below this top square), and $G_2$ is what happens when you let your construction lie on the floor. I use strings here because any variation of placing your construction on the floor would represent an isomorphic graph - you are just looking for the planar one. – Sergio Da Silva Feb 24 '14 at 21:00

Are these two graphs isomorphic?

2 Answers2