On the genus of the complete tripartite graph $K_{n,n,1}$

Valentas Kurauskas

Published 2016-12-23Version 1

For even $n$ we prove that the genus of the complete tripartite graph $K_{n,n,1}$ is $\lceil (n-1) (n-2)/4 \rceil$. This is the least number of bridges needed to build a complete $n$-way road interchange where changing lanes is not allowed. Both the theoretical result, and the surprising link to modelling road intersections are new.