Hay más grafos planares en $5n$ vértices de grafos bipartitos en $n$ vértices?

Question

Usted puede venir para arriba con una simple prueba de que $\exists n_0\in\mathbb{N}$ tal que $\forall n\in\mathbb{N}, \:n\ge n_0$ hay más bipartito gráficos en $n$ vértices de grafos planares en $5n$ vértices?

(O al revés, de hecho, estoy tratando de encontrar fuera de la orden, esto es justo lo que yo creo que es cierto.)

Esta es una tarea, por lo que estoy buscando asesoramiento en lugar de soluciones. Hasta ahora, he venido con el siguiente:

• De la fórmula de Euler, se sigue que para cada plano gráfico de $G=(V,\:E)$, es cierto que $|E| \le3|V|$. Por lo tanto, supongo, no es en la mayoría de las ${n^2\choose3n}$ diferentes grafos planares en $n$ vértices.
• Hay, al menos, $2^{n^2/4}$ diferentes grafos bipartitos en $n$ vértices (si elegimos el tamaño de cada "parte" a $n/2$).

Son estos pensamientos vale nada? Se siente como que debo elegir un enfoque diferente para este ejercicio, pero no puede pensar en otra cosa.

David

Close-up: Como EuYu señaló, mi original obligado para grafos planares no es correcta, ya que sólo toma gráficos con 3n bordes en cuenta. Sin embargo, la prueba propuesta por Ross Milikan sostiene.

Gracias por la ayuda de todos!

Answer 1

Este es un buen enfoque. Usted puede enlazado ${n^2 \choose 3n} \lt (n^2)^{3n}=n^{6n}$ considerando los factores en el numerador se $n^2(n^2-1)(n^2-2)\ldots (n^2-3n+1)$, el redondeo de todos ellos a $n^2$ e ignorando a las $(3n)!$ en el denominador. Este va a ser menos de $2^{n^2/2}$ $n$ lo suficientemente grande. Para encontrar la manera de un gran $n$ tiene que ser, toma de registros. Por supuesto, usted podría conseguir de una manera más rigurosa obligado, pero si sólo quieres probar que finalmente no son más bipartita de los gráficos de este es suficiente.