TAOCP 7.1.1 Exercise 80
A partial cube is, by definition, a connected graph that admits an isometric embedding into a hypercube.
Exercise 80. [27] A partial cube is an "isometric" subgraph of a hypercube, a subgraph in which the distance between two vertices are the same as they are in the full graph. The vertices of a partial cube can therefore be labeled in such a way that the distance from $u$ to $v$ is the "Hamming distance" between $l(u)$ and $l(v)$, namely $\nu(l(u) \oplus l(v))$. Algorithm I shows that every median graph is a partial cube.
a) Find an induced subgraph of the 4-cube that isn't a partial cube. b) Give an example of a partial cube that isn't a median graph.
Verified: yes
Solve time: 2m16s
A partial cube is, by definition, a connected graph that admits an isometric embedding into a hypercube. Hence any violation of connectedness already prevents a graph from being a partial cube.
(a) An induced subgraph of $Q_4$ that is not a partial cube
Take
$$ V = {0000,,1111} \subseteq Q_4, $$
and let $G$ be the induced subgraph of $Q_4$ on $V$.
In $Q_4$, two vertices are adjacent if and only if they differ in exactly one coordinate. The Hamming distance between $0000$ and $1111$ is
$$ \nu(0000 \oplus 1111) = 4, $$
so these vertices are not adjacent in $Q_4$. Therefore the induced subgraph $G$ has no edges.
Thus $G$ consists of two isolated vertices and is disconnected. Since every partial cube must be connected, $G$ is not a partial cube.
(b) A partial cube that is not a median graph
Let $C_6$ be the cycle graph on six vertices:
$$ v_0 - v_1 - v_2 - v_3 - v_4 - v_5 - v_0. $$
We first show that $C_6$ is a partial cube.
Label the vertices by binary strings of length $3$:
$$ \begin{aligned} v_0 &= 000,\ v_1 &= 001,\ v_2 &= 011,\ v_3 &= 010,\ v_4 &= 110,\ v_5 &= 100. \end{aligned} $$
Consecutive vertices differ in exactly one bit, so each edge of $C_6$ corresponds to a Hamming distance of $1$. Moreover, along the cycle, the graph distance between any two vertices equals their distance along this isometric embedding in the cube $Q_3$. Hence $C_6$ is an isometric subgraph of a hypercube, so it is a partial cube.
We now show that $C_6$ is not a median graph.
Consider the vertices $v_0, v_2, v_4$. Any vertex lying on shortest paths between each pair would have to simultaneously lie on geodesics in a cycle of length $6$. In $C_6$, the pairwise shortest paths between these three vertices are not simultaneously intersected by a unique vertex: there are two distinct candidates depending on direction around the cycle, and no single vertex lies on all three pairwise geodesics. Hence the median of $v_0, v_2, v_4$ does not exist uniquely.
Therefore $C_6$ is not a median graph.
Conclusion
An induced subgraph of $Q_4$ that is not a partial cube is any disconnected induced subgraph, for example ${0000,1111}$. A partial cube that is not a median graph is the 6_