# Which members of a particular family of graphs are either connected or planar?

I have a graph defined for any $n\in\mathbb{N}$, that is, $G_n=(V_n,E_n)$. Vertices are defined as every $n$-tuple over $\{0,1\}$. Two vertices $u=(u_1,u_2,\dotsc,u_n)$ and $v=(v_1,v_2,\dotsc,v_n)$ are adjacent when

$$\sum_{i=1}^n|u_i-v_i|=n-1$$

For which $n$ is the graph $G_n$ planar? For which $n$ is $G_n$ connected?

• Have you tried drawing $G_n$ for $n=0,1,2,3$ and looking for patterns? – Henning Makholm Aug 12 '16 at 11:24
• i will try that – MathIsTheWayOfLife Aug 12 '16 at 12:16
• Seems to me $G_n$ is connected iff $n$ is even. – bof Aug 14 '16 at 0:32
• $G_n$ is nonplanar (too many edges) for $n\ge4,$ planar for $n\le3.$ – bof Aug 14 '16 at 2:08
• @bof i thougt the same, but can i somehow prove that? – MathIsTheWayOfLife Aug 14 '16 at 7:21

The graph $G_n$ is planar if and only if $n\le3,$ connected if and only if $n$ is even. The proofs are simple, but I don't know how to write them down without introducing some notation.

Let $[n]=\{1,\dots,n\}.$ For $S\subseteq[n]$ define the function $f_S:V_n\to V_n$ so that $f_S(u_1,\dots,u_n)=(v_1,\dots,v_n)$ where, for $j\in[n],$ $$v_j=\begin{cases} \ \ \ u_j\ \ \ \ \text{ if }j\in S,\\ 1-u_j\text{ if }j\notin S. \end{cases}$$ For $i\in[n]$ let $f_i=f_{\{i\}},$ so that $f_i(u_1,\dots,u_n)=(v_1,\dots,v_n)$ where, for $j\in[n],$ $$v_j=\begin{cases} \ \ \ u_j\ \ \ \ \text{ if }j=i,\\ 1-u_j\text{ if }j\ne i. \end{cases}$$ Thus vertices $u$ and $v$ are adjacent in $G_n$ just in case $f_i(u)=v$ for some $i\in[n].$

For $S\subseteq[n]$ let $\prod_{i\in S}f_i$ denote the composition of the functions $f_i,\ i\in S$ (in any order, they commute).

Lemma. For $S\subseteq[n],$ $$\prod_{i\in S}f_i=\begin{cases} \ \ \ f_S\ \ \ \ \text{ if }|S|\text{ is odd,}\\ f_{[n]\setminus S}\ \ \text{ if }|S|\text{ is even.}. \end{cases}$$

Proposition 1. If $n$ is even then $G_n$ is connected.

Proof. Consider any vertices $u,v\in V_n.$ Let $S=\{j:u_j=v_j\}$, so that $f_S(u)=v.$ Since $n$ is even, $|S|$ and $|[n]\setminus S|$ have the same parity. It follows that $f_S$ is a composition of some functions $f_i,$ whence there is a path from $u$ to $v;$ namely, $f_S=\prod_{i\in S}f_i$ if $|S|$ is odd, and $f_S=\prod_{i\notin S}f_i$ otherwise.

Proposition 2. If $n$ is odd then $G_n$ is not connected; in fact, it is the sum of two connected components, which are isomorphic to each other.

Proof. Define the parity of a vertex $u=(u_1,\dots,u_n)$ to be the parity of $\sum_{j=1}^nu_j.$ Since $n$ is odd, any two adjacent vertices $u$ and $f_i(u)$ have the same parity, whence any two vertices that are connected by a path have the same parity. Conversely, if two vertices $u$ and $v$ have the same parity, then $v=f_S(u)$ where $|S|$ is odd (since $n$ is odd), whence $u$ and $v$ are connected by a path. Thus $G_n$ is the sum of two components, one containing all the even vertices, the other containing all the odd vertices. Of course these two subgraphs are isomorphic.

Proposition 3. $G_n$ is planar for $n\le3. Proof. Observe that$G_0=K_1,\ G_1=2C_1$(two vertices with a loop at each vertex),$G_2=C_4,$and$G_3=2K_4;$these are all planar graphs. Lemma. For a simple connected planar graph with$v$vertices and$e$edges, if$v\ge3$and there are no cycles of length$3,$then$e\le2v-4.$Proposition 4.$G_n$is nonplanar for$n\ge4.$Proof. For$n\ge4,$the graph$G_n$(if$n$is even) or a connected component of$G_n$(if$n$is odd) satisfies all the hypotheses of the lemma except planarity, but fails to satisfy the inequality$e\le2v-4,\$ so it can't be planar.