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?

  • $\begingroup$ 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. $\endgroup$ – Aravind Mar 29 '17 at 17:31
  • $\begingroup$ 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. $\endgroup$ – Aravind Mar 29 '17 at 17:32
  • $\begingroup$ 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. $\endgroup$ – Aravind Mar 29 '17 at 17:33
  • $\begingroup$ @Aravind how can I do this? 'constructing a planar embedding' $\endgroup$ – z00x Mar 29 '17 at 17:36
  • $\begingroup$ 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). $\endgroup$ – Aravind Mar 29 '17 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.