# Stability of medians in Median graphs

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.

-