Embedding the Gray Graph in a hypercube
The Gray Graph is the subgraph of a nine-dimensional hypercube induced by the bitvectors that have the form \( \{000,001,010,100\}^3 \) and that have at least two nonzero bits. I was excited this afternoon thinking that this embedding would give a second nonplanar cubic partial cube (the only known one being the Desargues Graph), but unfortunately it doesn't: e.g. \( 001001000 \) and \( 001010000 \) are at distance four in the graph via a path \( 001001000 - 001001001 - 001000001 - 001010001 - 001010000 \), but they have Hamming distance only two. In fact the graph is not a partial cube for any hypercube embedding. I guess that means it does provide another natural example of a hypercube subgraph that's induced but not isometric...