nLab acyclic graph

Contents

Contents

Idea

Recall that an undirected graph GG consists of a set VV of vertices and a set EE of unordered pairs of vertices. A path in GG is a finite sequence of vertices x 0,,x nx_0, \ldots, x_n such that each pair x ix i+1x_i x_{i+1} belongs to EE. If x n=x 0x_n = x_0, then the path is called a cycle. A graph is connected if it is nonempty and if for every distinct pair of vertices x,yx, y, there is a path for which x 0=xx_0 = x and x n=yx_n = y. A graph is acyclic if the only cycles are paths

x 0,,x n1,x n,x n1,,x 0x_0, \ldots, x_{n-1}, x_n, x_{n-1}, \ldots, x_0

where steps are retraced; an acyclic graph is also called a forest. A tree is a connected forest.

Each forest is a disjoint sum (a coproduct in the category of graphs) of trees. Removal of an edge of a tree results in a forest.

References

See also:

Last revised on December 25, 2023 at 21:46:01. See the history of this page for a list of all contributions to it.