Sé que el gráfico simple no tiene bordes y bucles paralelos. Mi pregunta es que tengo que dibujar el gráfico en seis vértices con secuencia de grados$(3,3,5,5,5,5)$. Dibujé el gráfico con la secuencia de grados dada y cada vez que obtuve el gráfico, que no es simple. ¿Existe un gráfico simple con esta secuencia de grados? Si no, ¿por qué?
Respuestas
¿Demasiados anuncios?
Lyra
Puntos
30
Según el Teorema de Havel-Hakimi, una secuencia de grados descendentes$\{a_1, \cdots ,\ a_k\}$ es gráfica si y solo si$a_1 \le k-1$ y$\{a_2 - 1, \cdots, a_{a_1+1}-1, a_{a_1 +2}, \cdots, a_k\}$ son gráficos.
Aplicando el teorema a su caso, tenemos$$\{5,5,5,5,3,3\} \iff \{4,4,4,2,2\}\iff\{3,3,1,1\}\iff\{2,0,0\}$ $. El último gráfico es evidentemente imposible.
Nada de imaginación teórica de la maquinaria que se requiere.
Llame a los vértices $v_1,v_2,v_3,v_4,v_5$, e $v_6$. Deje $v_1,v_2,v_3$, e $v_4$ ser los vértices de grado $5$. Sólo hay seis vértices, de modo que cada uno de estos vértices deben estar conectados a través de un borde a cada vértice del grafo. Por ejemplo, $v_2$ debe estar conectado a $v_1,v_3,v_4,v_5$, e $v_6$. Esto significa que $v_5$ $v_6$ están conectados a cada uno de los vértices $v_1,v_2,v_3$, e $v_4$ y por lo tanto debe tener grado mínimo de $4$: el grado de secuencia $(3,3,5,5,5,5)$ es imposible para un simple gráfico.
Si desea explorar más a fondo, este tipo de razonamiento nos lleva a la fácil la mitad de la Erdős-Gallai teorema, lo que da una simple computacional criterio para determinar si una secuencia es el grado de la secuencia de algunos simple gráfico. Este tipo de razonamiento muestra que una secuencia que falla el criterio no puede ser, posiblemente, un grado de secuencia; lo que prueba que cada secuencia que satisface realmente es el grado de secuencia de unos simples gráfico es más difícil. Ver también los comentarios aquí.
