Encontrar la circunferencia de un gráfico y demostrar que es la correcta

Question

Tengo que encontrar la circunferencia $g$ de la gráfica de abajo y demostrar que la circunferencia es al menos $g$ y como máximo $g$ .

Es evidente que este gráfico no tiene ningún ciclo de longitud $1$ o $2$ ya que es simple, así que $g \geq 3$ . No hay ninguna camarilla de tamaño $3$ por lo que no hay triángulo. Pero podemos encontrar un ciclo de longitud $4$ . ¿Es la justificación suficiente para $g \geq 4$ ? ¿Qué puedo hacer para mostrar la otra desigualdad?

Answer 1

Encontrar un ciclo de longitud $4$ es una prueba de que la circunferencia es como máximo $4$ . La circunferencia es la longitud del ciclo más corto, y hemos encontrado un ciclo de longitud $4$ Así que, o ese es el ciclo más corto, o hay un ciclo aún más corto que ese.

Para demostrar que la circunferencia es al menos $4$ tenemos que descartar todos los ciclos más cortos. Este gráfico es pequeño, por lo que podemos comprobar directamente que no $3$ -los ciclos existen probando todas las posibilidades. Otro enfoque para este grafo es demostrar que el grafo es bipartito, como lo demuestra la coloración de abajo:

(Los vértices rojos son una parte, los azules son la otra.) No puede haber ciclos Impares en un grafo bipartito, por lo que en particular no hay $3$ -ciclos.