In graph theory, the Lovász–Woodall conjecture is a long-standing problem on cycles in graphs. It says:
If is a -connected graph and is a set of independent edges in, then has a cycle containing, unless is odd and is an edge cut.
It was proposed independently by László Lovász in 1974 and by D. R. Woodall in 1977.
Many results in graph theory, starting with Menger's theorem, guarantee the existence of paths or cycles in a -connected graph. For 2-connected graphs, Menger's theorem is equivalent to the statement that any two vertices lie on a common cycle. A theorem of G. A. Dirac generalizes this claim: if a graph is -connected for, then for every set of vertices in the graph there is a cycle that passes through all the vertices in the set.[1]
Another corollary of Menger's theorem is that in 2-connected graphs, any two edges lie on a common cycle. The proof, however, does not generalize to the corresponding statement for edges in a -connected graph; rather, Menger's theorem can be used to show that in a -connected graph, given any 2 edges and vertices, there is a cycle passing through all of them.[2]
There is one obstacle to the stronger claim that in a -connected graph, given any set of edges, there should be a cycle containing . Suppose that the edges in form an edge cut: the vertices of can be separated into two sets and such that the edges in all join a vertex in to a vertex in, and are the only edges to do so. Then any cycle in can only use an even number of edges of : it must cross from to and from back to an equal number of times. If is odd, this means that no cycle can contain all of .
The Lovász–Woodall conjecture states that this is the only obstacle: given any set of edges, there is a cycle containing, except in the case that is odd and is an edge cut.
Woodall proposed the conjecture as one of several possible statements that would imply a conjecture made by Claude Berge: given a -connected graph with independence number, and any subgraph of with at most edges whose components are all paths, has a Hamiltonian cycle containing .[3] In 1982, Roland Häggkvist and Carsten Thomassen proved Berge's conjecture by proving one of the weaker statements proposed by Woodall.
As mentioned above, the case of the Lovász–Woodall conjecture follows from Menger's theorem. The case was given as an exercise by Lovász. After the conjecture was made, it was proven for by Péter L. Erdős and E. Győri and independently by Michael V. Lomonosov., and for by Daniel P. Sanders.
Other partial progress toward the conjecture has included versions of the result with a stronger assumption on connectivity. Woodall's paper included a proof that the conclusion of the conjecture holds if is -connected, and in 1977, Thomassen proved that the conjecture holds if is -connected. In 1982, Häggkvist and Thomassen proved that the conjecture holds if is -connected.
In 2002, Ken-ichi Kawarabayashi proved that under the hypotheses of the conjecture, is either contained in a cycle of or in two disjoint cycles.
In two publications in 2002 and 2008, Kawarabayashi claimed to have a proof on the conjecture, giving an outline for the proof and leaving several steps to future publications, but the full proof has not been published since.