2
$\begingroup$

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?

$\endgroup$
5
  • 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
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

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