I'm looking to prove or disprove the following conjecture:

Every polyhedral graph has a path cover with vertex disjoint, non-zero (length $\ge 1$) paths.

Any pointers to literature are appreciated. Thanks.

Some background: the conjecture is not true for arbitrary/planar/3-connected graphs, counterexamples include any bipartite graph where one of the partitions has < n/3 nodes, for example a claw.


Your Answer

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

Browse other questions tagged or ask your own question.