Stability of medians in Median graphs

Question

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.

Answer 1

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.

Answer 2

There is an easy proof based on the machinery of hyperplanes.

Proof 1. Fix four vertices $x,x',y,z \in X$ where $x,x'$ are adjacent. Let $D$ be a halfspace delimited by a hyperplane that does not separate $x$ and $x'$. Then $D$ contains at least two vertices among $x,y,z$ if and only if it contains at least two vertices among $x',y,z$. This amounts to saying that $D$ contains $m(x,y,z)$ if and only if it contains $m(x',y,z)$. Thus, the hyperplane separating $x$ and $x'$ is the only hyperplane that may separate $m(x,y,z)$ and $m(x',y,z)$. Because the distance between two vertices coincides with the number of hyperplanes that separate them, it follows that the distance between $m(x,y,z)$ and $m(x',y,z)$ is $\leq 1$, as desired. $\square$

There is an another elementary proof that avoids hyperplanes, but it depends on what you already know about median graphs.

Proof 2. Because a median graph always embeds isometrically into a Hamming cube $\{0,1\}^I$ (see for instance this answer), it suffices to show that the statement holds in $\{0,1\}^I$. Observe that, in this graph, the median operation can be described as follows: $$\left( (x_i), (y_i), (z_i) \right) \mapsto \left( \text{value taken at least twice among $x_i,y_i,z_i$} \right).$$ Fix four vertices $(x_i),(x_i'),(y_i),(z_i)$ where $(x_i)$ and $(x_i')$ are adjacent. This means that $(x_i)$ and $(x_i')$ differ on a single coordinate, say $i_0$. As a consequence, the median points $m((x_i),(y_i),(z_i))$ and $m((x_i'),(y_i),(z_i))$ may only differ on a single coordinate as well, namely $i_0$, which means that they either coincides or are adjacent. $\square$