We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) of $x,y$ is the cardinality of the set $\{ i \in \{0, ..., n-1\} : x(i) \neq y(i)\}$ (i.e. we count the positions on which $x$ and $y$ do not agree).


Fix a positive integer $k \leq n$. Two distinct elements of $\{0,1\}^n$ form an edge if their Hamming distance is at most $k$ (so they are in some sense "close" to each other). We denote the resulting graph on $\{0,1\}^n$ by $H(n,k)$.



> 
> Conjecture: If $G=(V,E)$ is a simple, undirected subgraph with $|V|=n$, then $G$ is isomorphic to some induced subgraph of $H(n,1)$ or $H(n,2)$.
> 
> 
> 


Is this conjecture true?



Conjecture on representing graphs within $\{0,1\}^n$
For $n\geq 8$, $K\_n$ with one edge removed is not such an induced subgraph. It's clearly not a subgraph of $H(n,1)$ since the latter is bipartite.


Suppose that graph is an induced subgraph of $H(n,2)$, say it's spanned on strings $x\_1,\dots,x\_n$ with $x\_{n-1},x\_n$ not connected. Observe we may assume $x\_1$ is the zero sequence, so the strings hence can be identified with at-most-two-element subsets of $[n]$ with pairwise symmetric differences of size at most two. First note that at least one of the sets has two elements (otherwise the induced graph would be complete), say $x\_2$. But then at most two sets have exactly one element, ones corresponding to elements of $x\_2$, let's say those are $x\_3,x\_4$ (we should also check for the case when $x\_{n-1}$ or $x\_n$ is one of those sets, but that case is easier). A little case work shows that if we have any four or more two-element sets which are pairwise intersecting, then they necessarily have a common element. Applying this to $x\_2,x\_5,\dots,x\_{n-2},x\_{n-1}$ and $x\_2,x\_5,\dots,x\_{n-2},x\_n$ have a common element. It follows $x\_{n-1},x\_n$ have a common element too, so they are connected in the graph. We need $n\geq 8$ here for there to be enough vertices, but this can be easily improved.


I believe a similar reasoning can be used to show that for a fixed $k$ and large enough $n$, $K\_n$ without an edge is not an induced subgraph of $H(n,k)$ -- I can show this for $k=3$ (I won't bother writing that down in detail since it's a lot of case work), but for general $k$ we need some general kind of general result that if we have a family of set with large pairwise intersections, then there is some "core" contained in all of them.


