Isometric embeddings of subdivided complete graphs in the hypercube

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollack [R.L Graham, H.Pollack On the addressing problem for loop switching, Bell System Technol., J. 50 (1971) 2495–2519], and Djokovic̀ [D. Djokovic̀, Distance preserving subgraphs of the hypercubes, Journal of Combinatorial Theory, Ser B41 (1973), 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we prove that a subdivision of a complete graph of order n ( n ⩾ 4 ) , is a partial cube if and only if this one is isomorphic to S ( K n ) , or there exist n − 1 non-subdivided edges of K n adjacent to a common vertex in the subdivision and the other edges of K n are subdivided an odd number of times.