Can you come up with a simple proof that $\exists n_0\in\mathbb{N}$ such that $\forall n\in\mathbb{N}, \:n\ge n_0$ there are more bipartite graphs on $n$ vertices than planar graphs on $5n$ vertices?
(Or the other way round, I am actually trying to find out the order, this is just what I think is true.)
This is a homework, so I am looking for advice rather than solutions. So far, I have come with the following:
- From Euler's formula, it follows that for every planar graph $G=(V,\:E)$, it is true that $|E| \le3|V|$. Therefore, I assume, there is at most ${n^2\choose3n}$ different planar graphs on $n$ vertices.
- There is at least $2^{n^2/4}$ different bipartite graphs on $n$ vertices (if we choose the size of each "part" to be $n/2$).
Are these thoughts worth anything? It feels like I should choose a different approach to this exercise, but cannot think of anything else.
David
Close-up: As EuYu pointed out, my original bound for planar graphs is not correct as it only takes graphs with 3n edges into account. However, the proof as proposed by Ross Milikan holds.
Thanks for everyone's help!