1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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