Looking to calculate the diameter of a graph of $2^{2016}$ binary strings. Compute the diameter of the graph G with $V (G) = \{0, 1\}^{2016}$ in which
two binary strings are connected if and only if they coincide in at most
one coordinate.
What I know right now: each vertex is connected to 2017 others and there are $2^{2016}$ total vertices.
 A: For each string $A$ and $k\in\{1,2,3\dots 2016\}$ we define $A_k$ as the string that coincides with $A$ in position $k$ only and $A_0$ as the string that coincides in zero positions. Therefore a path from string $A$ can  be described uniquely by a list of integers between $0$ and $2016$.
Given two strings $A$ and $B$, let $ \{a_1,a_2\dots a_n\}$ be the set of positions at which they differ if $A$ and $B$ differ at $1008$ or less positions and $\{a_1,a_2\dots a_n\}$ be the set of positions at which $A$ and $B$ are equal if they are equal at $1008$ or less positions. 
Then if we start at $A$ and do moves $a_1,a_2\dots a_{n}$ we end up at either $B$ or $B_0$, in the first case we have given a path with $1008$ edges or less , in the second case, if we do moves $a_1,a_2\dots a_n,0$ we have a path from $A$ to $B$ with $1008$ edges or less. This works in every case except when $A$ and $B$ differ in exactly $1008$ positions, in this case notice we get a path of length $1008$ by doing the moves in $\{1,2,3\dots 2016\}\setminus\{a_1,a_2\dots a_n\}$.
Now notice that if $A$ and $B$ are two strings and $A$ shares $n$ positions with $B$ then the number of positions in which $A_k$ is equal to $B$ is:


*

*$2016-n$ if $k=0$

*$2016-n+1$ if $k\neq 0$ and $A$ and $B$ are equal at position $k$

*$2016-n-1$ if $k\neq 0$ and $A$ and $B$ have different position $k$.


So if $n'$ is the number of positions in which $A_k$ and $B$ are equal we have $|n'-(2016-n')|\leq |n-(2016-n)|+2$.
Take two strings $A$ and $B$ differing in $1008$ positions. Then if $A'$ is a vertex reached from $A$ with less than $1008$ moves and $n'$ is the number of positions in which $A'$ differs from $B$ we obtain $|n'-(2016-n')|<2016$. Implying $A'\neq B,B_0$.
This proves the diameter is $1008$.
