# Almost All Graphs are Non-Planar

Gold Member

## 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 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!

## Answers and Replies

Related Calculus and Beyond Homework Help News on Phys.org
Office_Shredder
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?