Estoy luchando por ver cómo esto puede ser correcto cuando considero el ejemplo simple de un gráfico de tres vértices de modo que un vértice tiene un borde cada uno con los otros dos vértices. Tal gráfico es conexo y simple con un número impar de vértices y máximo grado dos. El número cromático del borde también es dos, ya que el gráfico solo necesita dos colores para colorear los dos bordes.
Entiendo que al visualizar un gráfico simple, el número cromático de su borde será o pero el problema es insistir en que en el caso de un grafo conexo simple con vértices impares siempre será y simplemente no estoy siguiendo cómo llegar allí con mi simple contraejemplo como prueba de lo contrario.
De hecho, ha proporcionado un contraejemplo válido para el reclamo. Una ruta de 2 es coloreable de 2 bordes, y tiene . Por lo tanto, no es cierto que cualquier gráfico conexo con un número impar de vértices y tiene índice cromático .
De hecho, se sabe que para cualquier gráfico bipartito , sostiene que . Es decir, no importa si el número de vértices es par o impar; si el gráfico es bipartito, se puede colorear en 2 aristas.
Si esto es un ejercicio, quizás esté hablando de ciclos con un número impar de vértices, o algo más.
Thiago Paixão
bof