A nonempty connected subgraph of a tree. Between any two included vertices, it contains the unique tree path: its connectedness supplies a path, and the ambient tree has only one. Such subgraphs satisfy the Helly property. They need not contain every descendant of an included vertex in any chosen rooting, unlike the descendant-closed data-structure subtree convention.
A finite family of nonempty connected subgraphs of a tree with pairwise nonempty intersections has a common vertex. For a finite ambient tree, prove this by deleting a leaf of a tree . If one member is , pairwise intersection proves the result immediately. Otherwise remove from every member containing it. Each such member remains nonempty and connected and contains the unique neighbour of . Hence every pair still intersects, even if its original intersection consisted only of , and mathematical induction applies. This is the Helly property specialized to trees.

Articles by others on the same topic (0)

There are currently no matching articles.