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: It has been pointed out that there is a simpler way to phrase the question. We are trying to find the minimum number of edges necessary for a graph on a torus which has both face-width at least n and edge-width at least n.

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!

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

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: It has been pointed out that there is a simpler way to phrase the question. We are trying to find the minimum number of edges necessary for a graph on a torus which has both face-width at least n and edge-width at least n.