Conjecture There exists a fixed constant so that every -vertex cubic graph without a cut-edge has at least perfect matchings.
Problem Let be a cyclically 4-edge-connected cubic graph and let be a cycle of . Must there exist a cycle so that ?
Conjecture Every bridgeless cubic graph has two perfect matchings , so that does not contain an odd edge-cut.
Conjecture Every 3-connected cubic planar bipartite graph is Hamiltonian.
Pentagon problem ★★★
Question Let be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?
5-flow conjecture ★★★★