I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.

Let $G(V,E)$ be a graph in which all vertices are degree 4. To simplify suppose there are no loops, and no repeated edges between vertices. An example would be to take a $d \times d$ square lattice and identify vertices and edges along opposite sides giving you a graph with $|V| = (d-1)^2$ on the torus (incidentally this graph has the property that it ``looks the same'' from any vertex). Now take any $v \in V$, and let $C$ be a circuit (no repeated edges) that starts and ends at $v$. Let $\text{len}(C) = L$, and suppose $C$ crosses itself $r$ times (i.e. there are $r$ vertices for which all 4 edges incident at the vertex are in $C$).

What is the minimum value of $L$?

If anyone can tell me if this problem is solved somewhere, or what general techniques are known to attack these kinds of problems, I'd really appreciate it. The actual graph that I'm interested in is more complicated than the one I mention here, but it is not completely random and has some symmetry. But all vertices are either degree 3 or 4, and some repeated edges are allowed (but no loops).

Edit: In view of the first comment below, let me make the question slightly interesting by requiring that the circuit is not a contractible loop on the torus.

Also let me provide another example in which I can also ask the same question. Let $G(V,E)$ be constructed by drawing $m$ latitudes and $n$ longitudes on the sphere. Then $|V| = mn + 2$ counting the north and south pole as vertices. Then let $C$ be a path (no repeated edges, and cannot visit the north or south pole in between) whose end points are the north and south pole. In this graph, all vertices except the north and south pole are degree 4. If $C$ crosses itself $r$ times, what is the minimum length of $L$ that makes it possible?

  • $\begingroup$ Without further conditions, you cannot say more than the trivial lower bound $L \geq 2r$ since all vertices in $C$ could have degree $4$. $\endgroup$ – Tony Huynh May 13 at 2:04
  • $\begingroup$ @TonyHuynh I made some edits to the question. $\endgroup$ – Rahul Sarkar May 13 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.