Results 1 to 2 of 2

Math Help - Complement graph not planar

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    England
    Posts
    5

    Complement graph not planar

    Hello,


    I have the following question:
    Let G be a simple graph with 2 connected components. Each component has at least 3 edges.


    Prove that G's complement graph is not planar.


    Now what I thought would make sense is that all the edges in the complement graph cross each other so it can't be planar, and also tried to solve in with Euler chararcteristic, unsuccessfuly.


    Any help is appriciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Complement graph not planar

    Since each component has at least 3 edges, it has at least 3 vertices. Therefore, the complement contains K3,3, doesn't it?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Planar graph
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 20th 2012, 11:43 PM
  2. Replies: 5
    Last Post: December 22nd 2010, 01:42 AM
  3. Planar graph
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: July 24th 2010, 07:21 AM
  4. is this graph planar?
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: March 3rd 2010, 01:32 PM
  5. isomorphic graph, planar graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 08:13 AM

Search Tags


/mathhelpforum @mathhelpforum