Tutte graph is a counterexample for the Tait's conjecture stating that all cubic graphs are Hamiltonian. For the non-hamiltonian graphs - is it true that all vertices of any such graph can be covered by a set of cycles?

  • 1
    $\begingroup$ Each vertex is on a cycle, so the answer to your question would be yes. But this is probably not what you mean. Please clarify. $\endgroup$ – Leen Droogendijk May 21 '14 at 6:46
  • $\begingroup$ Tait's conjecture says that every planar 3-connected cubic graph is Hamiltonian. In every at least 2-connected graph, each vertex is on a cycle, and so yes, the graph can be covered with a set of cycles. If you don't restrict to at least 2-connected graphs, there are cubic planar graphs with vertices not participating in any cycles. $\endgroup$ – Perry Elliott-Iverson May 21 '14 at 12:51
  • $\begingroup$ Sorry, I meant to say "covered by a set of mutually non-overlapping cycles". $\endgroup$ – Leonid May 21 '14 at 13:54

Yes, each cubic polyhedral graph can be covered by a set of mutually disjoint cycles. This is a trivial consequence of Petersen's theorem that states that every bridgeless, cubic graph has a 1-factor. Since a polyhedral graph is bridgeless, it has a 1-factor. Removing this 1-factor leaves a regular graph of degree 2, which is a union of disjoint cycles.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.