- #1

jgens

Gold Member

- 1,581

- 50

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

_{5}or

*K*

_{3,3}. Therefore, if I can show almost all graphs have subgraphs homeomorphic to

*K*

_{5}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*

_{5}or

*K*

_{3,3}. Can anyone give me a nudge in the right direction?

Thanks!