graph theory: show that for k=4 hesse diagram is not a planar graph

Question

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$

For the set $A$ with $k$ elements, $k>0$

look at the diagram as a graph, it's vertices are the members of $P(A)$

show that when k=4, the graph is not a planar graph.

my answer: it's easy becuase we have a sentence that say in a planar bigraph, we have at most 2*n-4 edges.I already showed that hesse diagram as a graph is a bigraph, so we can see that when k=4, we have (4*($2^4$))/2 = 32 edges, but for it to be a planar graph we can have at most 2 * $2^4$-4 = 28 edges, which is not the case so it's not planar.

now I have a question that I struggle with

show that for every k >= 4, the graph is not planar.

can someone help me?

Answer 1

The same approach works for $k>4$. The number of edges is $k2^{k-1}$ (we are just counting the number of edges in a $k$-dimensional hypercube), but for the graph to be planar you need $e\le 2v-4=2^{k+1}-4$. Since $2^{k+1}-4<k2^{k-1}$ whenever $k\ge 4$, you are done.

Answer 2

An alternative to the other answer: Note that if $B\subseteq A$, then $P(B)$ is a subgraph of $P(A)$. So if $A$ has more than $4$ elements, just take any subset $B$ of $4$ elements. This $P(B)$ is non-planar, as you've already shown, and so $P(A)$ must be non-planar as well as it contains a non-planar subgraph.