small circle inside embedding of complete graph in the plane

Question

On the web, I found this beautiful drawing of the complete graph on 13 vertices:

It is on the Geometry Daily tumblr page. A computer scientist drew a more interactive version up to about 40 vertices.

---

One way to think about it is the complex roots of unity $V = \{ e^{2\pi i k/3}: 0 \leq k < 13 \}$ and all the lines between them

\[ \ell_{a,b} = \big\{ t e^{2\pi i a /13} + (1-t) e^{2\pi i b /13}: 0 < t < 1 \big\} \]

Oops! This is not a complete graph since we are missing $\ell_{k, k+1}$. Is there a name for this new graph and it's realization on $\mathbb{R}^2$.

---

I'd like to know what's been said about this embedding. In the middle, for odd $n$ there is definitely a circle. The envelope of the lines $\ell_{k, k+6}, \ell_{k+6, k+12}, \dots$

In fact, a circle for every arithmetic sequence $C_{k,d} = \text{envelope} \{ \ell_{k, k+d}, \ell_{k+d, k+2d}, \dots \}$

These are orbits of the billiard on the circle or something.

What are the radii of these circles as a function of number of points?

Answer 1

Consider the $n$th roots of unity as the vertices of our complete graph. Consider the triangle formed by joining a vertex to the two vertices directly opposite of it, let us call this triangle a wedge.

Note that this is only for odd $n$, for even $n$ the triangle is degenerate since each vertex has a partner directly opposite. The smallest circle is not present for even $n$, instead we get a larger circle by considering triangles formed by joining each vertex to the ones adjacent to the one it's opposite. In the same sense, as $n$ becomes larger, it is easy to see that we will form several concentric circles by joining successively further apart vertices. We will not handle these cases here, but the analysis is similar.

Back to our problem at hand. Let us restrict ourselves to odd $n$. By symmetry the circle is centered on the origin. The edges of our wedge are precisely tangents of the circle, so the problem reduces to finding the closest distance of the edges to the origin. Consider the complete graph as embedded in the unit circle. Then our wedge subtends an arc of angle $\frac{2\pi}{n}$ which means that the smaller of its angles is $\frac{\pi}{n}$.

This means that the radius of the complete graph (which is $1$), the radius of the small circle $r$, and a segment of a wedge edge forms a right-angled triangle with hypotenuse $1$. The angle opposite $r$ is given as $\frac{\pi}{2n}$. Together, this means that the radius of the circle is given by $$r = \sin\left(\frac{\pi}{2n}\right)\approx \frac{\pi}{2n}$$ where we can use the small angle approximation for sufficiently large $n$. Numerically for $n=13$, this is approximately $r_{13} \approx 0.1205$ for a unit radius graph.

Because I have far too much time on my hands, I took the $13$ vertex graph from the interactive plot you linked above and I measured the radius of the small circle in pixel length. The small circle had a radius of approximately $30$ while the total graph had a radius of approximately $249$. The ratio is approximately $0.12048$ so this is numerical support of our proof.