Deje $G_n$
ser un grafo con vértices $v_1, v_2, v_3,\dots, v_n$,
donde hay un borde entre el $v_i$
y $v_j$
si y sólo si $v_i$
divide $v_j$
o viceversa.
Hay un valor de $n$
tal que $G_n$
no es planar,
es decir no puede ser dibujado en el plano sin aristas de intersección?
Si es así, ¿cuál es el menor valor de $n$
para que esto ocurra?
A modo de ejemplo,
el dibujo de abajo muestra que
$G_{12}$ es planar.
Respuesta
¿Demasiados anuncios?
$G_{14}$ es planar: Desde su $G_{12}$ croquis, reubicar $7$ en la $1{-}2{-}6$ triángulo. Esto permite que usted agregue $14$ con los bordes de la $1$, $2$, $7$. Y el primer $13$ puede ser colocado en cualquier lugar en el exterior de la región.
Uno fácilmente se ve que los cinco números de $1,2,4,8,16$ formar un $K_5$, por lo tanto $G_{16}$ no es planar.
Entonces, ¿qué acerca de la $G_{15}$? Resulta que íbamos a tener un $K_{3,3}$ con vértices $1,2,3$ e $6,12,m$ si hubo otro múltiplo común de a$2 $ e $3$ disponible. Mientras que no hay tal $m$, tenemos $5$, que está vinculado de forma indirecta a $3$ través $15$ e a $2$ través $10$. Por lo tanto, $G_{15}$ no es planar.
