(adsbygoogle = window.adsbygoogle || []).push({}); 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 toK_{5}orK_{3,3}. Therefore, if I can show almost all graphs have subgraphs homeomorphic toK_{5}orK_{3,3}, this would complete the proof.

My thought on this was to letP_{n}denote the probability that a random graph onnvertices is not planar and then show lim_{n -> ∞}P_{n}= 1. However, I need some help on how to show which graphs onnvertices contain subgraphs homeomorphic toK_{5}orK_{3,3}. Can anyone give me a nudge in the right direction?

Thanks!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**