Are there connected, planar graphs of size $N$ with minimal degree $\left( N−2 \right)$ for any $N \in \mathbb{N}$? 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:


*

*Is it impossible to draw such a graph with $N=7$ and no crossings?

*If not, what is the minimum number of crossings $C(N)$ needed?

*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
 A: 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. 

A: 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)$.
