# 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:

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:

• Not an answer, just a formalisation of your question: "Are there connected, planar graphs of size $N$ with minimal degree $N-2$ for any $N\in\mathbb N$?" – Tomas Aug 29 '13 at 19:26
• @Tomas I'm not quite sure if "regular" is the right word to be using here, since I am only requiring at least $\left( N-2 \right)$ connected edges. See my graph for the $N=5$ case. – Ryan Aug 29 '13 at 19:29
• Yes, indeed, that was too fast. I edited it. – Tomas Aug 29 '13 at 19:31
• I am pretty sure the answer is going to be no for 7 vertices. A graph is planar iff it does not contain $K_5$ or $K_{3,3}$ as minors. If you have at least 7 vertices all of which have degree at least 5 then (possibly by collapsing edges) you can get a $K_5$. – James Aug 29 '13 at 19:41

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

• So if you replace $(N-2)$ with $(N-m)$ you find that $N \leq\lfloor \frac{(6+m)+\sqrt{(6+m)^2-48}}{2}\rfloor$. – fretty Aug 29 '13 at 20:02
• Drak's answer for my first question was very concise, but I think I'll accept this answer because it targets the more general problem. And I'm surprised you actually found a closed-form solution for my second question, regardless if it is an optimal lower bound or not. – Ryan Aug 29 '13 at 21:27
• I feel his answer is a little bit vague and uses more complicated theorems than needs be. The method I use above is nothing more than combining two simple inequalities. – fretty Aug 29 '13 at 21:31
• To be honest question $1$ is really a special case of question $2$ but with $\text{cr}(G)=0$...notice you end up solving an inequality with the same right hand side. – fretty Aug 29 '13 at 21:33

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.

• Are you sure? Degrees sometimes decrease when you contract.... – N. S. Aug 29 '13 at 21:22