# Determining planarity of sub-graph of $Q_4 = (V, E)$

Let $Q_4 = (V, E)$ the graph of the four-dimensional cube. $V=\{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111\}$ Is $G'=(V, E \setminus \{\{0010, 0011\},\{0110,0111\}, \{1010, 1011\}, \{1110, 1111\}\})$ is a planar graph?

I have tried to find a counter-example using the theorem that states that if a graph is planar then it implies that $|E|\leq 3|V|-6$ but It doesn't work, so I think that it is planar, but how can I show this?

• Your statement is incorrect: a graph is planar implies that $|E| \leq 3|V|-6$. The latter inequality does not imply that the graph is planar. – Aravind Mar 29 '17 at 17:31
• Also this graph is bipartite; for a bipartite planar graph, we have: $|E| \leq 2|V|-4$. This inequality is tight for this graph $G'$; $|V|=16$ and the number of edges is 32-4, becuase $Q_4$ has 32 edges. – Aravind Mar 29 '17 at 17:32
• This means that you if you were trying to prove that it is planar, then you should try to construct a planar embedding where every face has exactly 4 edges. – Aravind Mar 29 '17 at 17:33
• @Aravind how can I do this? 'constructing a planar embedding' – z00x Mar 29 '17 at 17:36
• You have to place the vertices on a plane and draw the edges of the graph with no two edges crossing each other. A graph is called planar if it has such a drawing (called planar embedding). – Aravind Mar 29 '17 at 17:40