1. Not finding help here? Sign up for a free 30min 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!

Almost All Graphs are Non-Planar

  1. Nov 9, 2011 #1

    jgens

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    Prove that almost all graphs are not planar graphs.

    2. Relevant equations

    Kuratowski's Theorem

    3. The attempt at a solution

    Kuratowski's Theorem states that a graph is planar if and only if it does not contain a subgraph homeomorphic to K5 or K3,3. Therefore, if I can show almost all graphs have subgraphs homeomorphic to K5 or K3,3, this would complete the proof.

    My thought on this was to let Pn denote the probability that a random graph on n vertices is not planar and then show limn -> ∞Pn = 1. However, I need some help on how to show which graphs on n vertices contain subgraphs homeomorphic to K5 or K3,3. Can anyone give me a nudge in the right direction?

    Thanks!
     
  2. jcsd
  3. Nov 9, 2011 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think you can hit this with a sledgehammer. Consider just the case where n is divisible by 5 and divide up the vertices into collections of 5. Can you show that if n is big the probability is high that you get at least one K5?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Almost All Graphs are Non-Planar
  1. Graph planarity (Replies: 1)

Loading...