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: