$(k,n)$-binary graphs

Question

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.)

Answer 1

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.