Results 1 to 2 of 2

Thread: isomorphic graph, planar graph

  1. #1
    Junior Member
    Jun 2008

    isomorphic graph, 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 (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.
    Last edited by georgel; May 5th 2009 at 05:20 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    May 2009
    Tokyo, Japan
    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.
    Last edited by TiRune; May 9th 2009 at 02:23 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Maximal 4-regular Planar Graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 7th 2011, 07:24 PM
  2. Replies: 5
    Last Post: Dec 22nd 2010, 02:42 AM
  3. Planar graph
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Jul 24th 2010, 08:21 AM
  4. is this graph planar?
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Mar 3rd 2010, 02:32 PM
  5. Planar Graph problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 15th 2007, 01:26 AM

Search Tags

/mathhelpforum @mathhelpforum