What is the maximum number of distinct edges that can be contained in a cycle in a $k$-connected graph?

Question

I know the theorem below.

Theorem. (Dirac [1960]) If $G$ is a $k$-connected graph (with $k \geq 2$ ), and $S$ is a set of $k$ vertices in $G$, then $G$ has a cycle including $S$ in its vertex set.

What I am wondering is whether there is a similar result for $k$ edges. That is to say:

Problem 1. Let $G$ be a $k$-connected graph (with $k \geq 2$ ). If $S$ is an edge set in $G$, then what is the upper bound for $|S|$ to ensure that there exists a cycle in $G$ that includes $S$ in its edge set?

Through my research, I have discovered some properties for some special values of $k$.

• Show any two edges in a 2-connected graph lie on a cycle
• Given a 3-connected graph, show that any 3 edges lie on a common cycle, unless the edges form an edge-cut

Among them, I find the second statement interesting. It implies that the statement $|S| = k$ in the previous question may not hold unless certain additional constraints are imposed.

---

In fact, we can ask a related question as follows:

Problem 2. Given a $k$-connected graph, does any $k$ edges lie on a common cycle, unless the edges form an edge-cut?

If the above statement is negative, then can we provide a counterexample?

Answer 1

The Lovász–Woodall conjecture is essentially the same as this question. It says:

If $G$ is a $k$-connected graph and $L$ is a set of $k$ independent edges in $G$, then $G$ has a cycle containing $L$, unless $k$ is odd and $L$ is an edge cut.

Note that we only want to avoid $L$ being an edge cut if $k$ is odd. That's because, if $L$ is an edge cut and we want to traverse all the edges in $L$, we will go from one side of the cut to the other $k$ times. If $k$ is odd, we will end up on a different side from where we started, and won't be able to finish the cycle. If $k$ is even, however, there is no problem.

As far as I can tell, the conjecture does not yet have a proof. Here are a few interesting results:

• In 1982, Häggkvist and Thomassen proved that if $G$ is actually $(k+1)$-connected (but $L$ still has only $k$ edges) then $G$ has a cycle containing $L$.
• In 1985, Péter Erdős and Győri proved the conjecture for $k=4$.
• In 1996, Sanders proved the conjecture for $k=5$.
• In 2001, Kawarabayashi proved that under these conditions, $G$ either has a cycle containing $L$, or two disjoint cycles which together contain $L$. The paper claims to lead to the proof of the conjecture, and some later papers cite it that way, but I don't think this has panned out. It is still significant progress towards the conjecture!
• In 2019, Knappe and Pitz proved that if $G$ has no odd cut of size at most $k$ (a slightly different condition from $G-L$ being connected) then $G$ has a closed walk through $k$ prescribed edges, which no longer have to be independent.

---

By the way, even though asking for the edges in $L$ to be independent is enough to avoid the obviously-impossible cases, it is not necessary. Another reasonable condition is to ask for $L$ to be a linear forest: that is, a forest in which all components are paths.

This version of the question appears more general, but in fact we can reduce it to the question with independent edges. Suppose that $G$ is a $k$-connected graph, $L$ is a $k$-edge linear forest in $G$, and $L$ has a path component with $\ell > 1$ edges in it. Then we can:

1. Delete the $\ell-1$ interior vertices of that path from $G$ (and delete the $\ell$ edges of the path from $L$).
2. Add an edge joining the remaining two vertices of the path to $G$ (if it is not already present) and to $L$.

The result is that $G$ is now only $(k-\ell+1)$-connected, but $L$ has only $k-\ell+1$ edges. Repeat on every component of $L$, and we end up in the case of the Lovász–Woodall conjecture.

The condition "if $k$ is odd, $L$ must not be an edge cut" changes slightly after we perform these transformations. The final result after all these steps are done must satisfy it. For the original linear forest $L$, the condition is:

If the number of components of $L$ is odd, then deleting all edges and all degree-$2$ vertices of $L$ must not disconnect $G$.

This condition is necessary, for the same reason that the edge cut condition is necessary for the Lovász–Woodall conjecture.