Suppose $G$ is an infinite graph with vertices labelled as $v\_{i,j}$ such that $i,j$ are positive integers (so we assume that there are denumerable many vertices of the graph). For any two positive integers $i,j$ we join the vertex $v\_{i,j}$ with all the vertices $v\_{k,i+j}$ for every $k \in \mathbb{N}.$


Is the chromatic number of the graph $G$ necessarily infinite?



If $G$ is an infinite graph where $v_{i,j}$ is joined with $v_{k,i+j}$ for all $k,i,j$ then is the chromatic number of G always infinite?
The chromatic number is indeed infinite.


Assume that there is a proper coloring in finitely many colors. Denote by $S\_i$ the set of colors of the vertices having the form $v\_{k,i}$ (for some $k$). There are two equal sets, say $S\_i$ and $S\_j$ with $i<j$. Then the color of $v\_{j-i,i}$ lies in that set, and therefore is also a color of some vertex $v\_{k,j}$; but those vertices are adjacent.


