|WikiProject Mathematics||(Rated B-class, Mid-priority)|
Examples: union of shortest tree paths
Section Median_graph#Examples says:
observe that in a tree, the union of the three shortest paths between pairs of the three vertices a, b, and c is either itself a path, or a subtree formed by three paths meeting at a single central node with degree three.
However, for nodes Q, U, and X in the picture, the union of their shortest paths amounts to the subtree rooted at V (this node has degree 2). That is, the union is neither itself a path, nor a subtree formed by three paths meeting at a single central node with degree three. Did I misunderstand something, or are there some cases missing in the argument about trees being median graphs? - Jochen Burghardt (talk) 19:31, 3 October 2013 (UTC)
- The sentence in question is about trees viewed as undirected graphs, rather than rooted trees viewed as directed graphs. In your example, the subtree formed by the union of paths for Q, U, and X consists of three paths meeting at the degree-three node S. —David Eppstein (talk) 20:14, 3 October 2013 (UTC)