In graph theory, the Lovász–Woodall conjecture is a long-standing problem on cycles in graphs. 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. It was proposed independently by László Lovász in 1974 and by D. R. Woodall in 1977.
Background and motivation Many results in graph theory, starting with Menger's theorem, guarantee the existence of paths or cycles in a k-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 k-connected for k ≥ 2, then for every set of k vertices in the graph there is a cycle that passes through all the vertices in the set. 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 k edges in a k-connected graph; rather, Menger's theorem can be used to show that in a k-connected graph, given any 2 edges and k − 2 vertices, there is a cycle passing through all of them. There is one obstacle to the stronger claim that in a k-connected graph G, given any set L of k edges, there should be a cycle containing L. Suppose that the edges in L form an edge cut: the vertices of G can be separated into two sets A and B such that the edges in L all join a vertex in A to a vertex in B, and are the only edges to do so. Then any cycle in G can only use an even number of edges of L: it must cross from A to B and from B back to A an equal number of times. If k is odd, this means that no cycle can contain all of L. The Lovász–Woodall conjecture states that this is the only obstacle: given any set L of k edges, there is a cycle containing L, except in the case that k is odd and L 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 k-connected graph G with independence number α(G), and any subgraph F of G with at most k − α(G) edges whose components are all paths, G has a Hamiltonian cycle containing F. In 1982, Roland Häggkvist and Carsten Thomassen proved Berge's conjecture by proving one of the weaker statements proposed by Woodall.
Partial results As mentioned above, the k = 2 case of the Lovász–Woodall conjecture follows from Menger's theorem. The k = 3 case was given as an exercise by Lovász. After the conjecture was made, it was proven for k = 4 by Péter L. Erdős and E. Győri and independently by Michael V. Lomonosov., and for k = 5 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 G is (2k − 2)-connected, and in 1977, Thomassen proved that the conjecture holds if G is (3k − 1)/2-connected. In 1982, Häggkvist and Thomassen proved that the conjecture holds if G is (k + 1)-connected. In 2002, Ken-ichi Kawarabayashi proved that under the hypotheses of the conjecture, L is either contained in a cycle of G or in two disjoint cycles.
Current status 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.
References
