A pseudoforest is an undirected graph in which every connected component has at most one cycle

Intuition: If a connected undirected graph on $n$ vertices has $n-1$ edges, then it is a tree. If a connected undirected graph on $n$ vertices has $n$ edges, then it has exactly one cycle (i.e. an underlying tree, with an additional edge which closes the cycle). Hence, a pseudoforest consists of connected components, where each component on $k$ vertices consists of either $k-1$ or $k$ edges.

Directed pseudoforests

The concept of a pseudoforest can also be extended to include directed graphs. A directed pseudoforest is a directed graph in which each vertex has at most one outgoing edge; that is, it has outdegree at most one. In the special case where each vertex has outdegree exactly one, the graph is called a functional graph

Problems

• Room Assignments³
• Tug of War¹²

See also

• Functional graph

External links

• Pseudoforest