Lovász–Woodall conjecture

For 2-connected graphs, Menger's theorem is equivalent to the statement that any two vertices lie on a common cycle.

[3] Another corollary of Menger's theorem is that in 2-connected graphs, any two edges lie on a common cycle.

Woodall proposed the conjecture as one of several possible statements[2] 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.[5] In 1982, Roland Häggkvist and Carsten Thomassen proved Berge's conjecture by proving one of the weaker statements proposed by Woodall.

[7] After the conjecture was made, it was proven for k = 4 by Péter L. Erdős and E. Győri[8] and independently by Michael V.

[10] Other partial progress toward the conjecture has included versions of the result with a stronger assumption on connectivity.