Are there connected, planar graphs of size $N$ with minimal degree $\left( N−2 \right)$ for any $N \in \mathbb{N}$?

Question

I was doing a bit of doodling today with graphs of N vertices, trying my best to make sure that every vertex had minimal degree of $\left( N-2 \right)$ without any crossings. I was able to form graphs for $N=3$, $N=4$, $N=5$ and $N=6$ cases, but I can't find a way to do it for the $N=7$ case. Below are solutions for the $N=4$ through $N=6$ cases:

Here are some questions I have:

1. Is it impossible to draw such a graph with $N=7$ and no crossings?
2. If not, what is the minimum number of crossings $C(N)$ needed?
3. Is there a simple generalization for $N$ points and minimal degree of $\left( N-m \right)$ per vertex? I'm mainly curious if there is a closed-form expression for the upper limit as a function of $m$.

A somewhat related problem:

• Water, Gas and Electricity Puzzle

Answer 1

I can answer question $1$ for you. From this you will see how to answer question $3$ for yourself.

Suppose we have a simple, connected, planar graph with $N$ vertices and $e$ edges with minimal vertex degree $N-2$.

Then the handshaking lemma says:

$N(N-2)\leq 2e$

But also we know for such graphs that if $N\geq 3$ then $e\leq 3N-6$ (see http://en.wikipedia.org/wiki/Planar_graph).

Thus for our graph we have:

$N(N-2) \leq 6N - 12$.

Solving gives $N \leq 6$ as you noticed in your experimentation.

UPDATE:

To answer question $2$ make use of the inequality $\text{cr}(G) \geq e-3N+6$ (see proof of crossing number inequality at http://en.wikipedia.org/wiki/Crossing_number_(graph_theory)).

This inequality plus our earlier inequality on $2e$ tells us that $\text{cr}(G) \geq \frac{N(N-2)}{2} - 3N + 6$, which for $N=7$ suggests you will never draw such a graph without needing $3$ or more crossings. I don't know if this is optimal.

Notice how this crossing number inequality only tells us that $\text{cr}(G)\geq 0$ for $N\leq 6$ as expected!

Again this inequality is always true and so you can do the same for minimum number of crossings for minimal degree $(N-m)$.

Answer 2

Contract two pairs of vertices you get a minor that is a $K_5$ graph. Then Wagner's theorem states:

A finite graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor.