Graph with conditions

Question

G is a graph whose vertex set is $\{1,2, ... , 82\}$, vertices $i$ and $j$ are adjacent iff $|i-j| \mod 4 = 0 \text{ and } i \neq j$.

(a) Calculate the chromatic number of $G$.

(b) Is $G$ Eulerian?

(c) Is $G$ planar?

I'm not sure how to go on about part (a) or part (c), for part (b), I tested cases manually like adjacent vertices of $1$ are $\{5, 9, ... , 81\}$ which are $20$ vertices, since degree of each vertex is even, it is Eulerian.

For part (c) I believe it should be enough to prove that there is a $K_5$ or $K_{3,3}$ subgraph but I'm not sure how to do this.

Answer 1

Hint (a): Note that chromatic number of a complete graph $K_n$ is $n$ (Why?) and also think why this information is useful here (as an another hint, you can see the definition of complete graph).

Hint (b): When there are $20$ vertices and each vertex is adjacent to every other vertex, what is the degree of each vertex (This question is asked because for vertices $3$ and $4$, there is a difference)? Besides, we have some equivalence classes of nodes like nodes that are adjacent to $1$ can be represented by $[1]$ and similar to that, we have $[2]$, $[3]$ and $[4]$. If these are like equivalence classes, what can we say about them?

Hint (c): It is true that $K_5$ is not planar. What can we say about planarity of $K_n$ for $n \ge 5$?

Answer 2

Hint for (c). You are right to try to check if there is a $K_5$ or $K_{3,3}$ subgraph. Let's have a look for a $K_5$ -- what does this mean? It means that we have (distinct) vertices (ie natural numbers) $n_1$, $n_2$, $n_3$, $n_4$ and $n_5$ so that they are all mutually adjacent. That is, we must have $$ n_i \equiv n_j \mod 4 \quad \text{for all} \quad i,j \in \{1,2,3,4,5\}.$$ One can then try to come up with five numbers $\{n_1, ..., n_5\}$ satisfying these conditions.

Note that 'equivalence mod 4' is an equivalence relation: if $a \equiv b$ and $b \equiv c$ then $a \equiv c$ (mod 4). This makes it easier to find a complete subgraph, since we just need to find five connected points.

---

Now I've written this, it seems likely to me that you have stated the question incorrectly (although I could be mistaken!). Do you mean "$i$ and $j$ are adjacent if and only if $i \not\equiv j$ mod 4" (ie "are not equivalent mod 4" rather than "are equivalent mod 4")? The latter is quite easy: we just need five numbers, all of whose differences are a multiple of four. The former is harder: we need five numbers, none of whose differences are a multiple of four. (Question: is this possible?)

As noted in a comment below, a graph is planar if and only if it does not contain a subgraph that is a subdivision of a $K_5$ or a $K_{3,3}$; this is Kuratowski's theorem.