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. Rank 0 characterizes
trees, while 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.