Given a graph embedded on a torus, how many edges are necessary for noncontractible loops to be long?

Question

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!

Answer 1

There should be a nice proof, but here is a reference that proves something stronger and weaker. This paper by de Graaf and Schrijver proves that every graph embedded on the torus with face-width at least $n \geq 5$, contains the toroidal $\lfloor 2n/3 \rfloor$-grid as a minor. Note that the toroidal $\lfloor 2n/3 \rfloor$-grid has (almost) $8n^2/9$ edges. So any graph on the torus with face-width at least $n$ has at least (almost) $8n^2/9$ edges, which is pretty close to the conjectured answer of $n^2$.

Answer 2

Here is the idea of the proof that the number of vertices in such a graph is at least $n^2$. See step 7 for the hole in the proof. I believe it can be patched.
Edit: As was shown in comments there are a lot of problems with this attempt. I am in doubt whether it can be patched or not.

Step 1: Cut the graph at any shortest loop (its length $l\geq n$). You will get a graph on a cylinder (imagine it as a "vertical" cylinder) with a correspondence between edges and vertices on its bottom to edges and vertices at its top. Lets call these bottom edges as $e_1,\dots,e_l$ and top --- $e'_1,\dots,e'_l$.

Step 2: Take any shortest dual path between correspondent edges on the top and on the bottom of the cylinder. It corresponds to a noncontractible dual loop on the torus and its length $k\geq n$. Cut the cylinder at the vertices "just to the right of this path". Now we have a graph on the square with correspondence between vertices on its left to vertices on its right. Denote "left" vertices by $x_0,\dots, x_m$ and right by $x'_0,\dots, x'_m$, sorted from the bottom: $x_0$ and $x'_0$ are vertices at the bottom correspondent to $x_m$ and $x'_m$.

Step 3: Start $n$ dual paths $p_1,\dots,p_n$ at edges $e_1,\dots,e_n$. Assume $x=x_0$ are current left vertex and $x'=x'_0$ --- current right vertex.

Step 4: Suppose on this step $x=x_i$ is the current left vertex and $x'=x'_ j$ --- current right vertex. "Move up one of these vertices": if $i< j$ let $\widetilde x=x_{i+1}$ to be next current left vertex and if $j< i$ let $\widetilde x'=x'_ {j+1}$ to be the next current right vertex. In the case $i=j$ draw the shortest path from $x_{i+1}$ to $x'_ {i}$ and the shortest path from $x_{i}$ to $x'_ {i+1}$. At least one of them has length at least $n$. Choose it and let $\widetilde x= x_{i+1}$ or $\widetilde x'=x'_{i+1}$ correspondingly to the choice.

Step 5: Assume, that we have just defined $\widetilde x$ on step 4 (otherwise we have defined $\widetilde x'$ and this step should be rewritten correspondingly). Prolong $p_1,\dots,p_n$ to the shortest path from $\widetilde x$ to $x'$ avoiding intersections (all edges of $p_1,\dots,p_n$ should be different). To show it is possible define $d(v)$ to be a distance from vertex $v$ to $x'$ (length of the shortest path). Suppose last edge of $p_j$ joins vertices $v$ and $w$. Then $|d(v)-d(w)|=1$, since this edge is the part from the shortest path from $x$ to $x'$. Let $d_j=\min(d(v),d(w))$. On this step add to $p_j$ only edges connecting vertices of the same type (i.e. $|d(v)-d(w)|=1$ and $\min(d(v),d(w))=d_j$). Use only vertices between two shortest paths: between $\widetilde x$ and $x$ with $x'$. Note that all $d_j$ are different. This proves that $p_j$ will not intersect with others. Finally set $x=\widetilde x$.

Step 6: If $x\neq x_m$ or $x'\neq x'_m$ go to step 4. Otherwise go to step 7.

Step 7: Note that now we have $n$ dual paths $p_1,\dots,p_n$ from the bottom to the top of the square. All we need is to assure that they correspond to the cycles of the initial graph (because in this case each of these cycles has length of at least $n$). To achieve this, I believe, we should do step 5 more accurately.