Talk:Median graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Priority
 Field: Discrete mathematics

Examples: union of shortest tree paths[edit]

Example tree

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)
Ah ok, now I see. Thank you for your explanation. - Jochen Burghardt (talk) 20:24, 3 October 2013 (UTC)