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

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?

• What does "representable in $R^2$" mean? Jul 18 '19 at 4:39
• I just appended the definition, thanks.
– user636413
Jul 18 '19 at 4:52
• It depemds which numbers are in $G$. If only numbers divisible by 4 are in then it is planar since there is no connection.
– Aqua
Jul 18 '19 at 5:02
• @RobertZ What I want is to know if the graph described I can associate a "map", but I think it is necessary to be a planar graph
– user636413
Jul 18 '19 at 5:19
• The definition of representable is equivalent to planarity. Jul 18 '19 at 5:35

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$$).
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.