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


    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?

  2. jcsd
  3. Nov 9, 2011 #2


    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook