Are these two graphs isomorphic?

245 Views Asked by At

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

2

There are 2 best solutions below

3
On BEST ANSWER

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.

1
On

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?