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:

Graph of N points and (N-2) connections per point, from N=4 to N=6

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:

  • 1
    $\begingroup$ 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$?" $\endgroup$
    – Tomas
    Aug 29 '13 at 19:26
  • $\begingroup$ @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. $\endgroup$
    – Ryan
    Aug 29 '13 at 19:29
  • $\begingroup$ Yes, indeed, that was too fast. I edited it. $\endgroup$
    – Tomas
    Aug 29 '13 at 19:31
  • 1
    $\begingroup$ 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$. $\endgroup$
    – James
    Aug 29 '13 at 19:41

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.

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

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.


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

  • $\begingroup$ 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$. $\endgroup$
    – fretty
    Aug 29 '13 at 20:02
  • $\begingroup$ 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. $\endgroup$
    – Ryan
    Aug 29 '13 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – fretty
    Aug 29 '13 at 21:31
  • $\begingroup$ 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. $\endgroup$
    – fretty
    Aug 29 '13 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.