Let $G$ be a graph in which:
- Every vertex is represented as binary sequence having the length $k$. The number of vertices in such graph is $n=2^k$.
- Vertices are connected only when corresponding binary sequences differ on $j$ positions, where $j$ is odd number.
Is such graph bipartite? If so, prove it.
I tried to color vertices using BFS and I would say that is is bipartite, however I don't have any ideas how to prove it. Also sorry for any spelling mistakes I made, English is not my primary language.
The parities of the vertices incident to any edge in $G$ must be opposite, since $j$ is odd. Let all vertices whose bitstring has even parity receive one colour and all those whose bitstring has odd parity receive another; this gives a valid 2-colouring of $G$, proving its bipartiteness.