Partial cubes and their -graphs

The τ -graph G τ of a partial cube G has the equivalence classes of the Djoković–Winkler relation as vertices, two classes E and F being adjacent if some edges e ∈ E and f ∈ F induce a convex P 3 . It is shown that for every graph G there exists a median graph M such that G = M τ , that G τ is connected if and only if G is a Cartesian prime graph, and that for a median graph G its τ -graph is K n -free if and only if G contains no convex K 1 , n .