# What do we know about covering the edges of a graph by disjoint paths?

Two related things I have heard/know of are,

(1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?)

(2) That its NP-complete to decide if $k$ vertex disjoint paths can cover all the vertices of a graph.

• Are there edge analogues of these results?

• Does using the dual graph translate these results into their edge versions?

• If the line graph is a edge-to-vertex-dual then is there a vertex-to-edge-dual? (which will may be convert the question of finding a vertex cover by k vertex disjoint paths into a question of finding an edge cover by $k$ edge disjoint paths?)

• Although they are closely related, that is quite a lot of questions for one question. Stack Exchange usually works best with only one question or, at least, questions so closely related that it's likely that somebody will know the answers to all of them. Maybe this one's best left as it is, now, but something to bear in mind for next time. – David Richerby Sep 13 '14 at 7:20