Does a graph with $6$ vertices where each vertex degree is $4$ have to be planar?

Question

Does a graph with $6$ vertices where each vertex degree is $4$ have to be planar? I can draw a graph that is none planar, and another one which is planar. furthermore, there are $12$ arcs (can get it from $6*4 = 2$*arcs) so according to a known theory $12 \leq 3n - 6$ so it might be planar. but it doesn't have to be.

Thanks.

Answer 1

Yes it must be planar, if $G$ is required to be simple. Otherwise such a graph would have to have $K_{3,3}$ as a subgraph or $K_5$ as a subminor.

There is no such simple graph that contains $K_{3,3}$ as a subgraoh though.

So now it remains to show that $K_5$ cannot be a minor of such a graph. Then let us write the vertex-set of $G$ as $\{x_1,x_2,\ldots, x_6\}$ and suppose that $K_5$ is a subminor of $G$ where the vertices $v_1,v_2,,v_3,v_4,v_5$ of $K_5$ map to $x_1,x_2,x_3,x_4,x_5$, with $v_i$ mapping to $x_i$. Then each edge $v_iv_j$ in $K_5$ must map to $x_ix_j$ or $x_ix_6x_j$, there is only one such pair $i,j$ such that edge $v_iv_j$ may map to $x_ix_6x_j$. Thus, as $K_5$ has 10 edges, the induced subgraph of $G$ on $\{x_1,x_2,x_3,x_4,x_5\}$ must have at least 10-1=9 edges. This is impossible though, due to the fact thatr $x_6$ has degree 4 in $G$ and so does every vertex in $\{x_1,x_2,x_3,x_4,x_5\}$ i.e., 4 of $x_1,x_2,x_3,x_4,x_5$ have only 3 neighbours in $x_1,x_2,x_3,x_4,x_5$ so the induced subgraph of $G$ on $\{x_1,x_2,x_3,x_4,x_5\}$ has only $(4+ 3 \times 4)/2=8$ edges.

Answer 2

Yes. Up to isomorphism, there is only one graph with $6$ vertices, all with degree $4$, and that graph is planar.

Proof sketch:

Suppose $A$ and $B$ are graphs with $6$ vertices all with degree $4$. Then their complements, $\overline{A}$ and $\overline{B}$, are graphs with $6$ vertices all with degree $1$. But, up to isomorphism, there is only one such graph (it consists of three pairs of vertices, with the two vertices in each pair connected to each other). So $\overline{A}$ and $\overline{B}$ are isomorphic, which means that $A$ and $B$ are isomorphic.

So, up to isomorphism, there is only one graph with $6$ vertices all with degree $4$. Specifically, this graph is the one whose edges and vertices are those of an octahedron. This graph is planar.

Answer 3

To see this graph explicitly, first let $H$ be a 4-cycle on $\{x_1,x_2,x_3,x_4\}$. Then put one vertex $x_5$ inside $H$ and another vertex $x_6$ outside of $H$ and add the edges $x_ix_5$ and $x_ix_6$; $i=1,2,3,4$. Then the resulting graph is planar, has 6 vertices, and is 4-regular, and by the previous answer, is the only graph that has 6 vertices, and is 4-regular up to isomorphism.