TOPICS
Search

Pseudoforest


Pseudoforest

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 H, with edge count m=|E(H)| and vertex count n=|V(H)|, satisfies m<=n. A connected graph H has circuit rank m-n+1, 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.


See also

Circuit Rank, Connected Component, Forest, Graph Cycle, Pseudotree, Tree, Unicyclic Graph

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequence A134964 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Pseudoforest

Cite this as:

Weisstein, Eric W. "Pseudoforest." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Pseudoforest.html

Subject classifications