3
$\begingroup$

Let $G = (V, E)$ be a simple graph that can be embedded on a torus so that every region is bordered by exactly $3$ edges. Find (with a proof) all the possible values for the quantity $|V | − |E| + r$, where $r$ is the number of regions that the graph $G$ can split the torus.

So the torus will be covered in $C_3$'s connected to each other. I'm not really sure what to do with that information. Any help/hints will be appreciated.

$\endgroup$
1
$\begingroup$

A triangulated graph on a plane is maximal planar i.e. we cannot add a new edge without introducing an edge crossing. It is easy to see how on a plane a triangulated graph is maximal planar. By extending the similar logic, or you prove rigorously that a triangulated graph on a torus is also maximal (or maximal torus), i.e., you cannot add an edge without introducing an edge crossing.

Now a maximal torus graph is either maximal planar or non planar. If it is maximal planar, $\gamma(G)=0$ and if it is non-planar (and we know it can be embedded on a torus), $\gamma(G)=1$. Hence, the value of $|V|-|E|+r$ is either 2 or 0.

$\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.