I have ask this question in math.stackexchange, [here](https://math.stackexchange.com/questions/683217/genus-of-the-graph-k-4-2-2-2). Since, there is no answer and apart from that i feel that the problem is difficult, i would like to ask it here. The problem is to find the genus of $K\_{4,2,2,2}$. I want a theoretical technique(if possible), otherwise using sage programming is good enough. I have tried using sage for a week now, but my computer is too slow. Thanks for any help.


The graph $K\_{4,2,2,2}$ is a complete $4-$partite graph, that is, its vertex set can be partition into 4 disjoint parts of size 4, 2, 2 and 2, and any two vertices are adjacent if and only if they belong to different parts.



Genus of the graph $K_{4,2,2,2}$
I understand it's been years since this question was asked, but I figured I should give an answer for anyone still interested.


From the Euler equation, if $K\_{4,2,2,2}$ has genus 2, it would actually triangulate $S\_2$. Searching for triangular embeddings is much quicker than enumerating over all embeddings (as sage does). In fact, [Jungerman](https://core.ac.uk/download/pdf/82616223.pdf) was able to find a triangular embedding of $K\_{18}-K\_3$ in about half an hour back in the 1970s. Applying such an algorithm on $K\_{4,2,2,2}$ shows that it has no such embedding on $S\_2$.


Not only is $K\_{4,2,2,2}$ a subgraph of $K\_{10}$, as observed by @Douglas Zare, but it is a subgraph of $K\_{10}-K\_3$ as well, which has genus 3 (see [Youngs, "The Heawood Map-Coloring Problem--Cases 1, 7, 10"](https://core.ac.uk/download/pdf/82726666.pdf)). 


These two parts together show that the genus of $K\_{4,2,2,2}$ is 3.


