On the number of vertices and edges of the Buneman graph

摘要: In 1971, Peter Buneman proposed a way to construct tree from collection of pairwise compatible splits. This construction immediately generalizes arbitrary collections splits, and yields connected median graph, called the graph. this paper, we prove that vertices edges graph can be described in very simple way: given splitsS, correspond precisely subsetsS′ ofS such splits inS′ are incompatible pairs (S′, S) withS′ as above andS∈S′. Using characterization, it is much more straightforward than using prior constructions. We also recover an immediate consequence enumeration tree, is, number exceeds (by one), if only any two distinct inS compatible.