Dado un grafo no dirigido tal que cada vértice tiene grado exactamente $100$ . A haz es un conjunto de $10$ aristas conectadas al mismo vértice. Demostrar que el conjunto de todas las aristas se puede dividir en haces disjuntos.
El número total de aristas es $100n/2=50n$ donde $n$ es el número de vértices. Para el grafo completo con $101$ nodos (que es el mínimo número posible de nodos), ya no está claro cómo hacer la partición.
Sea $G$ sea nuestro grafo 100-regular con $n$ vértices. Obsérvese que podemos suponer que $G$ está conectado (si no, aplicamos el procedimiento a cada componente). Tomemos $5n$ botes de pintura, de todos los colores. Pon en cada bote pintura suficiente para pintar 10 bordes. Deja caer 5 botes en cada vértice.
Ahora $G$ es un grafo par, por lo que tiene un circuito euleriano. Elige un vértice cualquiera como vértice inicial y recorre el circuito. En cada vértice eliges un color que aún no esté agotado y pintas la arista por la que sales de ese color.
Al final has coloreado todos los bordes. Has dejado cada vértice 50 veces, por lo que se ha acabado toda la pintura. Los rayos destacan claramente, ya que son todos monocromáticos.
Tenga en cuenta que puede generalizar considerablemente el enunciado del problema sin cambiar la prueba de forma esencial. De hecho, puede ser un buen ejercicio probar hasta dónde se puede generalizar. Apuesto a que tu primer intento será mejorable.
Muy bonito, me ha recordado a la demostración del siguiente problema: Demostrar un $2k$ gráfico regular es $2$ -factorizable.
Interesante. La prueba que conozco de tu afirmación utiliza una transformación de grafos y aparte de utilizar un circuito euleriano es bastante diferente.
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.
