A hypergraph H is called a hypertree if it admits a host graph T such that T is a tree. In other words H is a hypertree if there exists a tree T such that every hyperedge of H is the set of vertices of a connected subtree of T. Hypertrees have also been called arboreal hypergraphs or tree hypergraphs.
Every tree T is itself a hypertree: T itself can be used as the host graph, and every edge of T is a subtree of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs.
Properties
Every hypertree has the Helly property (2-Helly property): if a subset S of its hyperedges has the property that every two hyperedges in S have a nonempty intersection, then S itself has a nonempty intersection (a vertex that belongs to all hyperedges in S).
By results of Duchet, Flament and Slater hypertrees may be equivalently characterized in the following ways.
The exact cover problem is solvable in polynomial time for hypertrees but remains NP-complete for alpha-acyclic hypergraphs.