TOPICS
Search

Pseudotree


Pseudotree

A pseudotree is a connected pseudoforest, i.e., an undirected connected graph that contains at most one graph cycle. Connected acyclic graphs (i.e., trees) are therefore pseudotrees.

Equivalently, a graph G with edge count m=|E(G)| and vertex count n=|V(G)| is a pseudotree iff it is connected and satisfies m<=n. For a connected graph, the circuit rank is m-n+1, so the bound says its circuit rank is 0 or 1. A pseudotree is therefore either a tree or a unicyclic graph. As a subclass of pseudoforests, pseudotrees are matchstick graphs and hence are also planar graphs and unit-distance graphs.

Some care is needed when encountering pseudotrees as some authors use the term to mean "a pseudotree that is not a tree." Such graphs are perhaps better known as unicyclic graphs for clarity.

The numbers of pseudotrees on 1, 2, 3, ... vertices are 1, 1, 2, 4, 8, 19, 44, 112, ... (OEIS A005703), the first few of which are illustrated above.


See also

Acyclic Graph, Circuit Rank, Connected Graph, Forest, Graph Cycle, Pseudoforest, Tree, Unicyclic Graph

Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

Pseudotree

Cite this as:

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

Subject classifications