A forest is a collection of trees.

Is there a similar notion for paths? e.g., a _______ is a collection of paths.

  • 1
    $\begingroup$ Not that I know of. You can call it a "path forest". $\endgroup$ Commented Feb 25, 2014 at 0:44
  • $\begingroup$ I haven't heard of a suitable term either. Just to speculate wildly, I conjecture that it's because "tree" and "path" do not refer to the same sort of object. A tree is a type of graph (connected acyclic) and a forest is where we drop the acyclic part. A path, at the basic level, is a sort-of-ordered subset of the vertices/edges (depending on how you want to define it) of a graph, and we just overload the term to mean a graph that doesn't have any other vertices or edges either. Then with this view there's no "collection of paths", and by inertia we haven't created one since. $\endgroup$ Commented Feb 25, 2014 at 0:51
  • $\begingroup$ @LukeMathieson I don't buy your argument that a path isn't a "real" graph at all. Paths are perfectly good graphs in their own right; the fact that their structure is so simple that they can be uniquely specified by listing their vertices in order doesn't affect that. $\endgroup$ Commented Feb 25, 2014 at 1:29
  • $\begingroup$ @DavidRicherby, I wasn't saying that they're not "real" graphs, I was speculating wildly about the historical reason we don't seem to have a neat, widely known term for disjoint union of paths. $\endgroup$ Commented Feb 25, 2014 at 1:31
  • $\begingroup$ @LukeMathieson: You probably also meant that a forest is where you drop the condition of being connected. In any case, even if there are historical reasons why collections of paths were not given a name, surely by the time people started studying path covers this should not longer have been true. One could just as easily ask: Spanning Forest : Path cover :: Forest : ? $\endgroup$ Commented Feb 25, 2014 at 6:14

1 Answer 1


Wikipedia says that a graph all of whose non-trivial components are paths is a linear forest. Alternatively, you could call it just a disjoint union of paths.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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