A pseudoforest is an undirected graph in which every connected component contains at most one graph cycle. A pseudotree is therefore a connected pseudoforest and a forest (i.e., not-necessarily-connected acyclic graph) is a trivial pseudoforest.
Equivalently, a graph is a pseudoforest iff every connected component , with edge count
and vertex count
, satisfies
. A connected graph
has circuit
rank
,
so the bound requires every component to have
circuit rank 0 or 1. Circuit
rank 0 characterizes trees, while circuit
rank 1 characterizes unicyclic graphs, so
these are precisely the possible components
of a pseudoforest.
Every pseudoforest is a matchstick graph and is therefore both a planar graph and a unit-distance graph.
Some care is needed when encountering pseudoforests as some authors use the term to mean "a pseudoforest that is not a forest."
The numbers of pseudoforests on 1, 2, 3, ... vertices are 1, 2, 4, 9, 19, 46, 108, 273 ... (OEIS A134964), the first few of which are illustrated above.