Let $k\leq n$ be positive integers with $n\geq 2$, and let $[n]=\{1,\ldots,n\}$. Let $V\_n=\{0,1\}^{[n]}$ be the set of all functions $f:[n]\to\{0,1\}$, and let 
$$E\_{k,n} =\big\{\{f,g\}: f,g\in V\_n\text{ and } |\{m\in [n]:f(m)\neq g(m)\}|=k\big\}.$$
We call $G\_{k,n} = (V\_n,E\_{k,n})$ the $(k,n)$-*binary graph*. It is easy to see that if $k,n$ have common divisors, then $G\_{k,n}$ is not connected (there is no path from the constant $0$-function to the function $g:[n]\to\{0,1\}$ where $g(1)=1$ and $g(m) = 0$ for $m\in[n]\setminus \{1\}$).


**Question.** If $k, n$ are relatively prime, is $G\_{k,n}$ connected? If yes, what is the length of the longest path?


(Will accept the first correct answer that addresses the first question, but will also upvote useful answers on the second question.)



$(k,n)$-binary graphs
No, the coprimality of $k$ and $n$ does not imply that $G\_{k,n}$ is connected. For a counterexample we consider the case $(k,n)=(2,3)$.


Represent a function $f\in V\_3$ by the sequence $(f(1),f(2),f(3))$. Then $V\_{2,3}$ is the disjoint union of two complete graphs with $4$ vertices each. The first one has vertices $(0,0,0)$, $(1,1,0)$, $(1,0,1)$, and $(0,1,1)$; the second one has vertices $(1,1,1)$, $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$.


More generally, if $k$ is even, then the parity of the sum of the entries remains invariant when passing along an edge. Hence $G\_{k,n}$ is not connected. 


