A Median graph is graph with the property, that for each three vertices $x,y,z$ there is a unique vertex $m(x,y,z)$ lying on shortest paths from $x$ to $y$, from $y$ to $z$ and from $z$ to $x$. Examples are trees, the Cayley graph of $\mathbb{Z}^n$ (with the standart generating set) and cross products of other median graphs.

Suppose, that $x$ and $x'$ are connected by an edge. Is it true, that $m(x,y,z)$ and $m(x',y,z)$ are also connected by an edge ?

EDIT: OK forgot about the case, that $m(x,y,z)=m(x',y,z)$. So I should better ask, whether $d(x,x')\le 1$, so that they are either connected by an edge or equal.


Here is an attempt to prove that the answer is yes.

Claim 1: Median graphs are bipartite.

This surely appears in the literature and is easy to verify. (Consider for a contradiction the shortest odd cycle and a median of 3 vertices on it: a pair of adjacent ones and a third one "opposite" of this pair.)

Claim 2: If $z \neq m(x,y,z)$ then there exists a vertex $z'$ adjacent to $z$ such that $d(x,z')=d(x,z)-1$ and $d(y,z')=d(y,z)-1$. Further, for each such vertex $z'$ we have $m(x,y,z')=m(x,y,z)$.

Let $m=m(x,y,z)$ and let $P(z,m)$ be as in Tony's comment. Then the neighbor of $z$ on $P(z,m)$ satisfies the claim. The second part of the claim holds as one can extend to $z$ the shortest paths between $z'$ and $x$ and $y$.

Main argument: By induction on $d(x,y)+d(x,z)+d(y,z)$. By Claim 1 $d(x,y)=d(x',y)\pm 1$ and $d(x,z)=d(x',z)\pm 1$. If the signs in both of these identities are the same then $m(x,y,z) = m(x',y,z)$ by Claim 2. Thus, wlog, $d(x,y)=d(x',y)+1$ and $d(x,z)=d(x',z)-1$.

If $z \neq m(x,y,z)$ then let $z'$ be as in Claim 2. We have $m(x,y,z')=m(x,y,z)$. As $d(x',z') \leq d(x,z')+1 = d(x',z)-1$, by the second part of the claim we have $m(x',y,z')=m(x',y,z)$. We can now replace $z$ by $z'$ and apply induction hypothesis.

We assume therefore that $z = m(x,y,z)$. Symmetrically, $y=m(x',y,z)$. We have

$(d(x,z) + d(z,y)) + (d(x',y)+d(y,z))=d(x,y)+d(x',z) \leq (d(x',y)+1)+(d(x,z)+1)$.

Thus $d(y,z) \leq 1$, as desired.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.