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?

  • 1
    $\begingroup$ What does "representable in $R^2$" mean? $\endgroup$ Jul 18 '19 at 4:39
  • $\begingroup$ I just appended the definition, thanks. $\endgroup$
    – user636413
    Jul 18 '19 at 4:52
  • $\begingroup$ It depemds which numbers are in $G$. If only numbers divisible by 4 are in then it is planar since there is no connection. $\endgroup$
    – Aqua
    Jul 18 '19 at 5:02
  • $\begingroup$ @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 $\endgroup$
    – user636413
    Jul 18 '19 at 5:19
  • 2
    $\begingroup$ The definition of representable is equivalent to planarity. $\endgroup$
    – M. Nestor
    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.


Your Answer

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