Partial cube

In graph theory, a partial cube is a graph that is an isometric subgraph of a hypercube. In other words, a partial cube is a subgraph of a hypercube that preserves distances—the distance between any two vertices in the subgraph is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

Firsov (1965) was the first to study isometric embeddings of graphs into hypercubes. The graphs that admit such embeddings were characterized by Djoković (1973) and Winkler (1984), and were later named partial cubes. A separate line of research on the same structures, in the terminology of families of sets rather than of hypercube labelings of graphs, was followed by Kuzmin & Ovchinnikov (1975) and Falmagne & Doignon (1997), among others.

Every tree is a partial cube. For, suppose that a tree T has m edges, and number these edges (arbitrarily) from 0 to m − 1. Choose a root vertex r for the tree, arbitrarily, and label each vertex v with a string of m bits that has a 1 in position i whenever edge i lies on the path from r to v in T. For instance, r itself will have a label that is all zero bits, its neighbors will have labels with a single 1-bit, etc. Then the Hamming distance between any two labels is the distance between the two vertices in the tree, so this labeling shows that T is a partial cube.

Every hypercube graph is itself a partial cube, which can be labeled with all the different bitstrings of length equal to the dimension of the hypercube.

...
Wikipedia