Let be G a finite graph such that his vertices are ...

Question

Let be $G$ a finite graph such that his vertices are natural numbers, and exist a edge between $n,m$ in $G$ if and only if $|m-n|$ is prime. $G$ is representable in $\mathbb{R}^2$?

Definition A representation of a graph $G$ in a metric space $X$ is a function $R$ from the vertices of G to regions (open, connected sets) in $X$ such that:

1. $R(v_1)∩R(v_2) =${ } when $v_1 \neq v_2$

2. Vertices $v_1$ and $v_2$ are adjacent in G if and only if $R(v_1) \neq R(v_2)$ and $R(v_1)$ shares infinitely many limit points with $R(v_2)$.

---

I'm trying to prove something and I got to this, will this be true?

Answer 1

The average degree of this graph is unbounded (if the vertices are all positive integers up to $n$, then every vertex will have about $n/\log n$ neighbors). A finite planar graph must have average degree $<6$. So this is hopeless even if you replace “prime” with pretty much any infinite set of integers (or for that matter, probably any set of size $4$).

Answer 2

The given graph $G$ could be NOT planar, i.e. not representable in $\mathbb{R}^2$. The planarity depends on the set of vertices of $G$.

Consider the Kuratowski's theorem and note that the graph $G$ may contain a copy of the bipartite graph $K_{3,3}$ which is not planar. Take for example the two disjoint and independent sets of vertices $U=\{1,7,11\}$ and $V=\{4,14,18\}$ where every vertex of $U$ is connected to every vertex of $V$. It follows that if $G$ contains the vertices $1,4,7,11,14,18$, then $G$ is not planar.

On the other hand, there are instances of $G$ which are planar. For example, if the set of vertices of $G$ are all multiples of a non prime number greater than $1$ (for example $4$ as in Aqua's comment) then the set of edges is empty and the graph is planar.