How many edge deletions make a $4$-regular graph on $7$ vertices planar?

Question

A $4$-regular graph on $7$ vertices is non-planar, it contains $14$ edges. How many edges would need to be deleted before it becomes planar? Is there a theorem to prove this?

I partitioned the 7 vertices into two separate sets A,B. A ={v1, v2, v3, v4} & B={v5, v6, v7}

After this I deleted edges between adjacent vertices in the same set, which left me with a triangle-free graph. After this I used a lemma that I found (sorry I can't find the name), it suggests that a triangle-free graph can only have at most 2v-4 edges.

This left me with 7 vertices and 10 edges. The graph is planar but I feel like my proof is very weak.

Answer 1

As stated, the question depends on the graph. Consider the two $4$-regular graphs shown below:

In the graph on the left, only one edge needs to be deleted to make it planar. Just delete any of the "diagonals". Then we can draw three of the remaining diagonals on the inside, and three others on the outside, and obtain a drawing of the remaining $13$-edge graph that has no crossings.

In the graph on the right, the $3$ top vertices and any $3$ of the bottom vertices form a $K_{3,3}$, which is not planar. So we need to remove some top-down edges. But if we remove only one of them, then the subgraph induced by the $3$ top vertices and the $3$ bottom vertices we haven't affected is still a $K_{3,3}$. So at least two edges need to be removed here.

We can ask:

• What is the least number $k$ such that there is some $4$-regular graph on $7$ vertices, $G$, such that we can delete $k$ edges from $G$ to make it planar? The first example above shows $k \le 1$, and if you can prove that no $4$-regular $7$-vertex graph is planar, you can conclude $k=1$ is best possible.
• What is the least number $k$ such that for every $4$-regular graph on $7$ vertices, $G$, we can delete $k$ edges from $G$ to make it planar? The second example above shows $k \ge 2$ (and there are actually two edges you can delete here to get a planar graph).

In fact, it turns out that these are the only two $4$-regular $7$-vertex graphs (on this page, we see that there are only two connected $4$-regular graphs on $7$ vertices, and there can't be any disconnected ones since each connected component must have at least $5$ vertices). So the answer to the second question is $k=2$.