0

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?

Ѕᴀᴀᴅ
  • 34,263
J. Schmidt
  • 333
  • 1
  • 9

1 Answers1

0

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.

user36196
  • 428
J. Schmidt
  • 333
  • 1
  • 9