# isomorphic graph, planar graph

• May 5th 2009, 04:04 PM
georgel
isomorphic graph, planar graph
I need help with the following two problems:

1) Is this graph planar?
http://i44.tinypic.com/9s8nkp.png

2) Are these two graphs isomorphic?
http://i41.tinypic.com/2l97fw5.png

I don't know what to do with these two problems, and I would be really grateful for all your hits and help.

For number 1, I've tried to use the corollaries of Euler's formula, but that gives me nothing, and for number two, I think it has something to to with the fact that one graph has a cycle of order 3, and the other one does not, but I don't know how to prove that isomorphisms preserve k-cyles (if they do).
Also, the first graph is bipartite, and the other one is not. Does isomorphism preserve this?

Edit: terribly sorry, the first one isn't bipartite..

Thank you.
• May 9th 2009, 08:13 AM
TiRune
For the planar graph, I think it's sufficient to 'smelt' the two top nodes together, which then changes into the $K_5$ which isn't planar, so the graph isn't planar. The 'smelted' graph is usually referred to as a 'minor' of the original graph, and any graph that has K_5 as a minor isn't planar.

"a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. An edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it used to connect."

The easiest way to show that that graphs aren't isomorphic is exactly what you sad, that the first graph has no 3-cycles (only four), and the 2nd one does (it has 3, 4 and 6 cycles). It really doesn't need much of a proof, you can just say that since isomorphisms preserve connections between any two points, if these two are isomorph and a, b, c is a cycle in the second graph, it has connections ab, bc and ca. the first graph must have the connections F(ab), F(bc) and F(ac) (so F(a)F(b), F(b)F(c) and F(a)F(c)) due to the isomorphism F, and thus the a,b,c cycle... this is not true so the graphs aren't isomorph.