TAOCP 7.1.1 Exercise 81

Exercise 81. [26] Is every median graph bipartite?

Verified: yes
Solve time: 2m21s

We correct the proof by using the median property directly on a triple involving the root and the endpoints of an edge.

Corrected Solution

Let $G$ be a median graph and fix a vertex $r \in V(G)$. For each vertex $v$, define its distance parity from $r$ by

$$ \chi(v) = d(r,v) \bmod 2. $$

We prove that every edge joins vertices of opposite parity.

Let $u,v$ be adjacent vertices, so $d(u,v)=1$. Consider the triple $(r,u,v)$. Since $G$ is a median graph, there exists a unique vertex

$$ m = m(r,u,v) $$

such that

$$ m \in I(r,u), \quad m \in I(r,v), \quad m \in I(u,v), $$

where $I(a,b)$ denotes the set of vertices lying on shortest paths between $a$ and $b$.

Now analyze the condition $m \in I(u,v)$. Since $d(u,v)=1$, any vertex lying on a shortest $u$-$v$ path must satisfy

$$ d(u,m) + d(m,v) = 1. $$

This forces $m$ to be either $u$ or $v$.

Since $m \in I(r,v)$, we have

$$ d(r,v) = d(r,m) + d(m,v) = d(r,u) + 1, $$

$$ d(r,v) = d(r,u) + 1. $$

Since $m \in I(r,u)$, we have

$$ d(r,u) = d(r,m) + d(m,u) = d(r,v) + 1, $$

$$ d(r,u) = d(r,v) + 1. $$

In either case,

$$ |d(r,u) - d(r,v)| = 1, $$

so $d(r,u)$ and $d(r,v)$ have opposite parity. Hence

$$ \chi(u) \ne \chi(v). $$

Let

$$ V_0 = {v : \chi(v)=0}, \quad V_1 = {v : \chi(v)=1}. $$

Every edge connects a vertex in $V_0$ to one in $V_1$, so $(V_0,V_1)$ is a bipartition of $G$.

Therefore every median graph is bipartite. ∎