Recall that an undirected graph consists of a set of vertices and a set of unordered pairs of vertices. A path in is a finite sequence of vertices such that each pair belongs to . If , then the path is called a cycle. A graph is connected if it is nonempty and if for every distinct pair of vertices , there is a path for which and . A graph is acyclic if the only cycles are paths
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.
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.