A branch point of a tree is a vertex of vertex degree at least three in the underlying undirected tree. Removing it separates the remaining tree into at least three connected components of a graph. This is a structural property of the graph, independent of which root of a tree is chosen.
The component count has a short proof. If has neighbors, each neighbor belongs to a component of . Two different neighbors cannot remain connected there, because that connecting graph path together with their two edges to would form a graph cycle. Every remaining vertex reaches one of the neighbors along its original route to . Hence has exactly components. The proof uses the unique-path property of a tree.[ref]
Graph Theory by Reinhard Diestel. Third edition2005, section1.5, pp.13–15: trees and unique paths; full text webhomes.maths.ed.ac.uk/~v1ranick/papers/diestel1.pdf
For an original example, take . Vertex has degree three, and deleting it leaves the three singleton components . Rooting at gives two children. Rooting at gives the root three children. Its undirected degree remains three in both cases.
The distinction matters at a root with only two children: its degree is two, so it does not meet this article's branch-point convention, even though a rooted drawing visibly splits there.
For a finite tree with at least two vertices, the degree-sum formula also giveswhere counts degree-one tree leaves. Subtract two per vertex from : degree-one vertices contribute−1, degree-two vertices contribute zero, and branch points contribute their excess above two. A degree-four hub therefore gives . A crossing in a drawing contributes nothing unless it is actually a graph vertex.
Articles by others on the same topic
There are currently no matching articles.