Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
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.
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.
Required, but never shown
4 years, 9 months ago