5 votos

Probar que dado gráfico que consta de vértices numeradas con los números no es euleriano

Tenemos el gráfico siguiente definición:

$$V(G_n)=\{1\leq m\leq n : m = pq\}$$ (so vetices of $G_n$ está compuesto de números) $$E(G_n)=\{\{i,j\}:i\perp j\}$$ (so vertices $i,j$ están conectados si y sólo si, se realtively de los números primos)

El problema nos pide demostrar que $G_{1000}$ no es euleriano. Así parece fácil - sólo necesitamos encontrar dos vértices, de tal manera que la paridad de grado de la primera es diferente que el de la segunda (o - incluso más sencillo encontrar un vértice con grado impar). Por desgracia he estado luchando con encontrar a esa pareja desde hace bastante tiempo ahora. Donde debo buscar?

3voto

justartem Puntos 13

Considerar el primer $223$ , considere la posibilidad de que los vecinos de $2\cdot 223$, todos ellos son el extraño compuesto de números a excepción de $3\cdot 223$.

Considere la posibilidad de que los vecinos de $4$. Todos ellos son el extraño compuesto de números. Estos dos conjuntos se diferencian por un elemento, por lo tanto vértices $4$ $2\cdot 223$ tienen órdenes de distinta paridad. Esto implica que hay un vértice de orden impar, por lo que la gráfica no es Euleriano.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X