Family of Graphs, Planarity. Consider a family of graphs $G_1,G_2,G_3,\dots$ where $G_n=(V_n,E_n)$ and $V_n=\{(x_1,\dots,x_n): x_i \in \{0,1\}, i=1,\dots,n\}$.
There is an edge between vertices $u=(u_1,...,u_n)$ and $v=(v_1,...,v_n)$ if and only if $u\neq v$ and $\sum_{i=1}^n (u_i - v_i)$ is divisible by $2$.
(For example, in $G_2$, $(1,0)$ is joined to $(0,1)$ by an edge, but neither is joined to $(0,0)$.)
i) What is $|V_n|$, the number of vertices of $G_n$.
ii) Draw the graphs $G_1, G_2, G_3$, labeling the vertices clearly.
iii) Show that, for any $n$, $G_n$ has two connected components, each of which is a complete graph.
iv)Show that $G_n$ is not planar for $n\geq 4$.
 A: It is important that you understand what it really means for any two $n$-tuples to be adjacent in this graph. Once this becomes clear, each part, especially iii) becomes clear. What does it mean for $\sum_{i=1}^n (u_i-v_i)$ to be divisible by $2$? Notice that if $u_i = v_i$ ($u$ and $v$ are the same in the $i$th position), then $u_i-v_i = 0$, that is the $i$th position contributes $0$ to the sum. So the only contributions made to the sum are from the $i$th positions that are different between $u$ and $v$. If this sum is divisible by $2$, in other words even, then we can say that two vertices are adjacent if and only if they differ in an even number of positions.


*

*As you've commented, $|V_n| = 2^n$, as the vertex set is composed of $n$-tuples whose entries are $0$ or $1$, and there are $2^n$ many such tuples ($2$ choices per entry).

*Here are the graphs $G_1 = 2K_1, G_2 = 2K_2, G_3 = 2K_4$ from left to right. Small examples should lead you to the light.

From 2. can you see what is going on here? Especially focus on $G_3$. What do you notice about the tuples in each copy of $K_4$. If you still don't understand why the edges connect the way they do, nothing beats good old brute force. That is, list your tuples and compute the sum $\sum_{i=1}^n (u_i-v_i)$ for each $u,v$.
I will include guidance in a spoiler for the rest.

We refer to $n$-tuples (vertices) as even (odd) if they contain an even (odd) number of $1$'s.

*
 
* Show that any two vertices $x$ and $y$ are adjacent if and only if they have the same parity.
  
*Conclude from the above that $G_n$ has two cliques, each of order $2^{n-1}$. The vertex set of one is composed of even $n$-tuples and the other is composed of odd $n$-tuples.

*To see that $G_n$ is not planar for $n \ge 4$, we can either use Kuratowski's Theorem or an edge counting argument (via Euler's formula, remember the $3n-6$ upper bound.) Essentially since the components are two cliques of order $2^{n-1}$, for $n\ge 4$ we will obtain both a $K_5$ and $K_{3,3}$ subdivision (trivially, since we have them as subgraphs.) So, instead if you independently prove that $K_5$ or $K_{3,3}$ are not planar, then that is sufficient as opposed to Kuratowski's Theorem.
 

If you require clarification feel free to comment.
