2
$\begingroup$

Following standard notations, we use $K_n$ to denote a complete graph with n vertices. We know that $K_1,K_2,K_3,K_4$ are planar graphs and a natural notion of vertex, edge, and face can be visualized easily. However, for all $n>4$, $K_n$ is not planar. So my question is: for arbitrary values of $n$, can we analytically find the minimal genus $g$ for which an embedding of $K_n$ on a two dimensional surface exists? If so, is there a systematic way to construct the minimal embedding? How many minimal embeddings are there?

P.S. I did some searches on google but did not find any satisfactory results. So I feel like I might be missing some trivial observation that prevents the existence of such embeddings. If so, please help me out!

$\endgroup$
4
$\begingroup$

The complete graph $K_n$ has genus $\left\lceil\frac{(n-3)(n-4)}{12}\right\rceil$ for $n\ge3$.

$\endgroup$

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.