3
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.