Minimum genus of torus necessary to embed complete graph $K_n$

306 Views Asked by At

You can embed complete graphs $K_1$, $K_2$, $K_3$, and $K_4$ on a genus $0$ torus (a sphere). The minimal genus of a torus on which you can embed $K_5$, $K_6$, and $K_7$ is a $1$. Then you need a torus of genus $2$ to embed ...

Is there a formula for any $K_n$, stating the minimum genus necessary to embed $K_n$ on a torus with that genus?

1

There are 1 best solutions below

0
On

Found it. All I needed to search for was "genus of complete graphs" :

http://mathworld.wolfram.com/GraphGenus.html

Ringel and Youngs 1968; Harary 1994, p. 118 :

$$\mbox{ceil}\left((n-3)(n-4)\over 12\right)$$

Please do edit the formula with MathJax.