To have $k$ friends there must be a least $k$ digits in each code. Also, if there are less than $2^k$ codes then all possible strings of $k$ digits do not exist among $S$. Assume $S$ has all possible strings of $k$ digits. It follows that each code has $k$ friends, as all possible friends are in $S$, with the maximum of $k$ friends. Now consider the set $S\setminus B$, where $B\subset S$. It follows that some friends of the remaining codes have been removed, thus we see $|S| \geq 2^k$.

Each code has n digits

Yes, I am saying $n\geq k$.

Sorry but i don't understand your solution

Here's my overly complicated solution. Nice problem though! Prerequisites: Let $\mathcal{B}_n$ be the set of $n-$digit binaries. Moreover, for any $\pi,\tau\in\mathcal{B}_n,$ let $\mathcal{H}(\pi,\tau)$ denote the Hamming Distance between $\pi$ and $\tau,$ which denotes the number of indices in which $\pi$ and $\tau$ differ. Finally, define the function $f:\mathcal{B}_n\to\{-1,1\}$ as such: $\forall \pi\in\mathcal{B}_n, \ f(\pi)=(-1)^t$ where $t$ is the number of $1$s in the representation of $\pi.$ Part One: It is easy, yet crucial to observe that if $\mathcal{H}(\pi,\tau)=1$ then $f(\pi)=- f(\tau).$ This is because $\pi$ and $\tau$ differ in exactly one index. Now, for each vertex $v$ in our graph $G,$ let $\pi_v$ be the binary $v$ represents. Let $G_1:=\{v\in G:f(\pi_v)=1\}$ and $G_{-1}=\{v\in G:f(\pi_v)=-1\}.$ By our previous observation, we can deduce that our graph $G$ is, in fact, a bipartition between $G_1$ and $G_{-1}.$ Therefore, by letting $e$ be the number of edges of $G$ we can easily deduce that $|G|$ is even as such: \[ k|G_1|=\sum_{v\in G_1}\deg v=e=\sum_{v\in G_{-1}}\deg v=k|G_{-1}|\implies|G_1|=|G_{-1}|\implies |G|=2 |G_1|\] Part Two: Select an arbitrary vertex $w.$ Let $D_0:=\{w\}.$ For each $i\geq 1,$ let $D_i:=\{v\in G:d(v,w)=i\}.$ In other words, $D_i$ is the set of vertices $v\in G$ such that the smallest path between $w$ and $v$ has $i$ edges. Moreover, for any $v\in D_i$ let $\deg_iv$ be the number of neighbours of $v$ in $D_{i-1}$ and $e_i$ be the number of edges between $D_i$ and $D_{i-1}.$ Claim 1: For any $i, \ v\in D_i, \iff \mathcal{H}(\pi_v,\pi_w)=i.$ If $t\leq m$ then by the induction Proof: This is trivial by induction. The claim is clearly true for $i=0,1.$ Assume the claim is true for $0,1,...,m$ and not true for $m+1.$ Therefore, for some $v\in D_{m+1},$ we have $\mathcal{H}(\pi_w,\pi_v)\neq m+1.$ Let $\mathcal{H}(\pi_w,\pi_v)=t.$ if $t\leq m,$ then by the induction hypothesis, $v$ would actually be part of $D_t,$ a contradiction. If $t>m+1$ then consider $u\in D_m$ such that $u\sim v.$ It is trivial to see that $t=\mathcal{H}(\pi_w,\pi_v)\leq\mathcal{H}(\pi_w,\pi_u)+\mathcal{H}(\pi_u,\pi_v)=m+1,$ another contradiction. Hence, the claim is true. Claim 2: If $u\in D_i, \ v\in D_j$ and $u\sim v$ then $|i-j|=1.$ Proof: Assume that $u\in D_i, \ u\in D_j$ and $u\sim v.$ Let $A$ be the set of indices in which $\pi_w$ and $\pi_u$ differ. Since $u\in D_i,$ by claim 1, $\mathcal{H}(\pi_w,\pi_u)=i$ so $|A|=i.$ Similarly, by letting $B$ be the set of indices in which $\pi_w$ and $\pi_v$ differ, we have $|B|=j.$ However, observe that The set $C$ of indices in which $\pi_v$ and $\pi_u$ differ is, in fact, the symmetric difference between $A$ and $B.$ Therefore, we have \[C=A\triangle B=(A\setminus B)\cup(B\setminus A)\implies\mathcal{H}(\pi_u,\pi_v)=|C|=|(A\setminus B)\cup(B\setminus A)|=|A\setminus B|+|B\setminus A|.\]However, we know that $u\sim v$ and thus, $\mathcal{H}(\pi_u,\pi_v)=1$ implying $1=|A\setminus B|+|B\setminus A|.$ Therefore, we must either have $B=A\cup\{x\}$ for some $x,$ or $A=B\cup\{y\}$ for some $y.$ In other words, we must have $||A|-|B||=1,$ but since $|A|=i$ and $|B|=j$ we get the desired equality, $|i-j|=1.$ Claim 3: For any $v\in D_i, \ \deg_i v\leq i.$ Proof: Assume that for some $v\in D_i, \ \deg_i v\geq i+1.$ Then, there are at least $i+1$ vertices $u\in D_{i-1}$ such that $u\sim v.$ In other words, (using claim 1) there are at least $i+1$ binaries $\pi_{u_1},\pi_{u_2},...,\pi_{u_{i+1}}$ such that $\mathcal{H}(\pi_{u_j},\pi_w)=i-1$ and $\mathcal{H}(\pi_{u_j},\pi_v)=1$ for any $j\in\{1,2,...,i+1\}.$ For each $j\in\{1,2,...,i+1\},$ let $A_j$ be the set of indices in which $\pi_{u_j}$ and $\pi_w$ differ. By the first condition, we have $|A_1|=|A_1|=\cdots=|A_{i+1}|=i-1.$ By the second condition, $\mathcal{H}(\pi_{u_j},\pi_v)=1,$ we know that there exist indices $x_1,x_2,...,x_{i+1}$ such that $A_1\cup\{x_1\}=\cdots=A_{i+1}\cup\{x_{i+1}\}$ Since $\pi_{u_1},\pi_{u_2},...,\pi_{u_{i+1}}$ are distinct binaries, $A_1,A_2,...,A_{i+1}$ are distinct sets, so $x_1,x_2,...,x_{i+1}$ are distinct indices. This, however, implies $|X_{i+1}\geq i$ since $x_1\neq x_2\neq\cdots\neq x_i\in X_{i+1}.$ This is an obvious contradiction. Using our claims, we will finally prove that for each $i\in\{0,1,...,k\}, \ |D_i|\geq k!/(i!\cdot (k-i)!).$ Assume this inequality holds for $0,1,...,m$ (it clearly holds for $0$ and $1,$ so the induction is valid). We will then prove it also holds for $m+1.$ In order to do so, we will double-count the number of edges between $D_{m+1}$ and $D_m$ (which we denote by $e_{m+1}$). By claim $2,$ a vertex $v\in D_m$ can only be linked to vertices from $D_{m-1}$ and $D_{m+1}.$ Hence, $v$ is linked to $\deg v-\deg_mv=k-\deg_m v$ vertices from $D_{m+1}.$ Thus \[e_{m+1}=\sum_{v\in D_m}(k-\deg_m(v))\geq\text{(by claim 3)}\sum_{v\in D_m}(k-m)=|D_m|(k-m)\geq\text{(by induction)}\frac{k!}{m!(k-m)!}(k-m).\]However, the number of edges between $D_m$ and $D_{m+1}$ is also obviously equal to the sum of $\deg_{m+1}$s over the vertices of $D_{m+1}$ (by the definition of $\deg_m$). Hence \[e_{m+1}=\sum_{v\in D_{m+1}}\deg_m v\leq\text{(by claim 3)}\sum_{v\in D_{m+1}}(m+1)=|D_{m+1}|(m+1).\]Combining the two latter equations, we get the desired inequality: \[|D_{m+1}|(m+1)\geq e_{m+1}\geq \frac{k!}{m!(k-m)!}(k-m)\implies |D_{m+1}|\geq \frac{k!}{m!(k-m)!}\cdot\frac{k-m}{m+1}=\frac{k!}{(m+1)!(k-m-1)!}.\]Finally, by adding all the inequalities we established for each $D_i$ we get the conclusion of part two: \[|G|=\sum_{i=0}^{\infty}|D_i|\geq\sum_{i=0}^{\infty}\frac{k!}{i!(k-i)!}=\sum_{i=0}^{k}\frac{k!}{i!(k-i)!}\text{(because the terms with $i>k$ are $0$)}=\sum_{i=0}^{k}\binom{k}{i}=2^k.\]