Linear forest

In graph theory, a branch of mathematics, a linear forest is a kind of forest where each component is a path graph,[1]: 200  or a disjoint union of nontrivial paths.

[3]: 130, 131  An acyclic graph where every vertex has degree 0, 1, or 2 is a linear forest.

[4]: 310 [5]: 107  An undirected graph has Colin de Verdière graph invariant at most 1 if and only if it is a (node-)disjoint union of paths, i.e. it is linear.

[6]: 13, 19–21 [7]: 29, 35, 67 (3, 6, 29)  Any linear forest is a subgraph of the path graph with the same number of vertices.

[8]: 55 According to Habib and Peroche, a k-linear forest consists of paths of k or fewer nodes each.

[2]: 245, 246 According to Faudree et al., a (k, t)-linear or (k, t, s)-linear forest has k edges, and t components of which s are single vertices; s is omitted if its value is not critical.

Isolated vertices are allowed, as are graphs with a single connected component. However, star graphs are not allowed as a subgraph (such as the claw in the second graph), and neither are cycles