Results 1 to 2 of 2

Math Help - graph theory question

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    Exclamation graph theory question

    Prove that if n = 12 and G is a simple graph on n vertices, then it is not possible for both G and the complement of G to be planar.

    I know that:
    for a graph to be non planar we have to either find a subgraph isomorphic to k5 or k3,3 or a subdivision of k5 or k3,3

    and I know that complement of G is connected if G is a graph on n vertices where n>= 2

    but I'm not sure if I'm on the right track and how exactly to combine these ideas to come up with a solid proof.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    This Wikipedia article gives a necessary condition for a graph to be planar: m\le 3n-6 where m is the number of edges. If m' is the number of edges in the complement graph, then m+m' is the number of edges in K_{12}. It seems to me that this necessary condition cannot hold for both graphs.

    That this condition is necessary can apparently be proved using Euler's formula (in the same article).

    I know that complement of G is connected if G is a graph on n vertices where n>= 2
    I am not sure about this: what if G consists of two connected points? Then its complement is two isolated points, i.e., not connected. Connectedness has to be taken care of because both Euler's formula and the condition above are true for connected graphs.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question in graph theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 7th 2011, 06:12 PM
  2. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 13th 2010, 02:32 PM
  3. Two Graph theory question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 8th 2009, 06:18 PM
  4. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 26th 2007, 07:10 AM
  5. Graph Theory Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 26th 2007, 06:21 AM

Search Tags


/mathhelpforum @mathhelpforum