1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Rather , isomorphic graphs, planar graph

  1. May 5, 2009 #1
    rather urgent :(, isomorphic graphs, planar graph

    I need help with the following two problems:

    1) Is this graph planar?

    2) Are these two graphs isomorphic?

    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. :(
    Also, the first graph is bipartite, and the other one is not. Does isomorphism preserve this?

    Please, help.
  2. jcsd
  3. May 6, 2009 #2
    Re: rather urgent :(, isomorphic graphs, planar graph

    Oh, the first one isn't bipartite, I got that wrong..
  4. May 6, 2009 #3


    Staff: Mentor

    Re: rather urgent :(, isomorphic graphs, planar graph

    My graph theory is pretty rusty and not very deep, but the first graph does not appear to be planar because of the edges that cross. Some information that might be helpful can be found at Wikipedia--search for "planar graph".
  5. May 7, 2009 #4
    Re: rather urgent :(, isomorphic graphs, planar graph

    If you want to prove that a graph isn't planar, you have to prove that it can not be "drawn" such that its edges don't cross, it is not enough to see that the current drawing isn't planar.
    (Sorry about my English, I don't know the right words..)

    Also, if anyone wanted to know, the graph indeed isn't planar, because it contains K3, 3, with some added edges.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook