Almost All Graphs are Non-Planar

[jgens]

Homework Statement

Prove that almost all graphs are not planar graphs.

Homework Equations

Kuratowski's Theorem

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 K₅ or K_3,3. Therefore, if I can show almost all graphs have subgraphs homeomorphic to K₅ or K_3,3, this would complete the proof.

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

Thanks!

 

[Office_Shredder]

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 K₅?