Demostrando que un "gráfico principal" está conectado

Question

Que el primer gráfico se define como el gráfico de todos los números naturales, con dos vértices están conectados si la suma de los números en los dos vértices se suma a un número primo. Demostrar que el primer gráfico está conectado.

Esto no tiene solución en el libro de texto. ¿Cómo debo plantear este problema? Estoy pensando en que todo está conectado a través de algún camino a $1$ pero no sé cómo hacerlo.

Answer 1

Daniel dejó entrever postulado de Bertrand. Desde que fue demostrado por Chebyshev, es en realidad un teorema.

Deje que todos los nodos $1,\dots,n-1$ estar conectado a $1$. Observamos $n$. Por Bertrand-el teorema de Chebyshev, hay un primer $p$ tal que $n < p < 2n$. Así, podemos escribir

$$p = x + n, \quad \text{for some $x < n$}.$$

Así, los nodos $x$ $n$ están conectados. Sin embargo, por la asunción, $x$ está conectado a $1$, lo que significa que $n$ también está conectado a $1$.

Answer 2

Esto es una exageración, pero usted puede mostrar algo más fuerte: es posible ir entre dos vértices de un uniformemente acotado número de pasos, es decir, hay una constante $K$ de manera tal que dos vértices están conectados por un camino de longitud en la mayoría de las $K$.

Natural de la $a$ se llama a un número de Polignac si existen infinitos pares de números primos cuya diferencia es $a$.

Suponga $y>x$. Tenga en cuenta que puede ir de $x$ $y$en dos pasos si no $z$ tal que $x+z,y+z$ son primos. Como un caso importante, usted puede ir de $x$ $y$si $y-x$ es un número de Polignac.

Pintz ha demostrado recientemente (página 3) que hay una constante $C$ de manera tal que cada intervalo de $[n,n+C]$ contiene un número de Polignac.

Para demostrar que hay un camino de$x$$y$, tomar un Polignac número $x-a \in [x-C,x]$ e ir de $x$ $a$(nota su diferencia es una de Polignac número y $a \leq C$). Del mismo modo, ir de $y$ $b$(donde $b \leq C$).

Ahora lo que necesita para conectar $a$$b$, donde ambos números están delimitadas por $C$. Usted puede hacer esto en un acotado número de pasos a través del postulado de Bertrand.