Stability of medians in Median graphs

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.

• Next botany - Do plant-plant interactions inhibit growth?
• Previous physiology - Would muscle fatigue still occur if aerobic conditions for a working muscle is maintained?