If we are given a graph embedded on a torus, with the following properties, what is the minimum number of edges it can have?
- Any noncontractible loop is comprised of at least n edges.
- Any noncontractible dual loop is comprised of at least n edges.
- Any noncontractible loop drawn on the torus intersects the graph at least once.
(The third condition is just to rule out cases where we embed a small planar graph on the torus, and trivially satisfy the first two conditions, there being no noncontractible loops)
We use the following definitions:
A loop is a series of edges, with each consecutive pair sharing a (different) common vertex, and with the first and last sharing a common vertex. It is noncontractible if the path formed by tracing along these edges is noncontractible on the torus.
A dual loop is a series of edges, with each consecutive pair sharing a (different) common face, and with the first and last sharing a common face. The name is because these edges form a loop on the dual graph. Likewise, it is noncontractible if it is noncontractible on the torus.
I believe that the answer is $n^2$ for even n, $n^2 + 1$ for odd n. The equality case, I think, is a square lattice on the torus, but rather than identifying horizontal and vertical lines, as is usually done to put a grid on the torus, you identify lines at 45 degrees to the grid. (Or slightly off 45 degrees, if n is odd)
It seems like a simple statement, but I haven't been able to find out whether this is true.
Thanks for any help! Graham
Edit: Whoops - rather than face-width, the second condition is asking about the edge-width of the dual graph. Apologies for the confusion!