teoría de grafos: demostrar que para k=4 el diagrama de Hesse no es un grafo plano

Question

En esta imagen se puede ver el diagrama de hesse de $\subseteq$ en $P(\{x,y,z\})$

Para el conjunto $A$ con $k$ elementos, $k>0$

Si consideramos el diagrama como un gráfico, sus vértices son los miembros de $P(A)$

demostrar que cuando k=4, el gráfico no es un gráfico plano.

mi respuesta: es fácil porque tenemos una frase que dice que en un bigraph planar, tenemos como máximo 2*n-4 aristas.Ya demostré que el diagrama de Hesse como gráfico es un bigraph, así que podemos ver que cuando k=4, tenemos (4*( $2^4$ ))/2 = 32 aristas, pero para que sea un gráfico plano podemos tener como máximo 2 * $2^4$ -4 = 28 aristas, que no es el caso por lo que no es planar.

ahora tengo una pregunta que me cuesta

demostrar que para cada k >= 4, el gráfico no es plano.

¿puede alguien ayudarme?

Answer 1

El mismo enfoque funciona para $k>4$ . El número de aristas es $k2^{k-1}$ (sólo estamos contando el número de aristas en un $k$ -hipercubo de dimensiones), pero para que el gráfico sea planar se necesita $e\le 2v-4=2^{k+1}-4$ . Desde $2^{k+1}-4<k2^{k-1}$ siempre que $k\ge 4$ has terminado.

Answer 2

Una alternativa a la otra respuesta: Tenga en cuenta que si $B\subseteq A$ entonces $P(B)$ es un subgrafo de $P(A)$ . Así que si $A$ tiene más de $4$ elementos, basta con tomar cualquier subconjunto $B$ de $4$ elementos. Este $P(B)$ es no planar, como ya has demostrado, y por lo tanto $P(A)$ debe ser no plano, ya que contiene un subgrafo no plano.