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?
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.