Deje $G$ ser simple grafo no dirigido con el grado de todos los vértices es de al menos 5. Probar o refutar que $G$ contiene subgrafo $K_4$.
Se me ocurrió esta pregunta cuando yo estábamos tratando de encontrar Ramsey número $R(4,3)$. Creo que mi conjetura es correcta, pero soy incapaz de demostrarlo. Si alguien tiene alguna idea por favor compartir conmigo. Gracias de antemano !
La completa tripartita gráfico de $K_{3,3,3}$ $6$- gráfico regular en $9$ vértices y ha cromática número$3$, por lo que no contiene $K_4.$
Por Frigyes del teorema, un simple gráfico con $9$ vértices y más de $27$ bordes debe contener $K_4$ como un subgrafo, y $K_{3,3,3}$ (también conocido como el Frigyes gráfico de $T(9,3)$) es el único de $K_4$libre de simple gráfico con $9$ vértices y $27$ bordes.
Si $\chi(G)=3$, el gráfico puede contener cualquier $K_4$ como un subgrafo:
El gráfico anterior es sólo una $K_9$ sólo con $9$ bordes eliminado, en particular, de una $K_{3,3,3}$, con cromática de número de $3$, como se desprende de la imagen (no par de vértices con el mismo color está unido por una arista, pero la gráfica tiene un montón de embedded triángulos).
Por otro lado, no es difícil demostrar que ningún gráfico en $9$ vértices con más de $27$ bordes tiene un subgrafo isomorfo a $K_4$. Bastante decepcionante y no incluso sorprendente, ya que un gráfico de cumplimiento de estas restricciones está llena de triángulos y casi completa:
Claramente, ya que la suma de los grados a lo largo de los 9 vértices debe ser, debe haber un vértice con grado de al menos $6$, lo que significa que sólo el 2 vértices son aisladas a partir de este vértice. Seleccione el vértice de mayor grado (grado-$6$ o más) y etiquetarlo como $A$ y los vértices conectados, el "conjunto enlazado", como $\{B,C,D,E,F,G\}$. Cada uno de estos tendrá un mínimo adicional $4$ enlaces para que además del enlace a $A$, así que al menos $2$ de estos, en cada caso, se encuentran dentro del conjunto enlazado. Así que esto le da 6 vértices y un mínimo de 6 aristas en el conjunto enlazado, que se puede conectar como un anillo para evitar triángulos. Y luego los otros dos verrtices, $\{H,I\}$ puede ser conectado a cada punto en el anillo (pero no de la otra) para evitar cualquier $K_4$.
Un diagrama de este:
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.
