Teoría de gráficas: como hacer la demostración siguiente...
- Sea G una gráfica sin ciclos y conexa tal que todos sus vértices tienen grado impar. Demuestre que el número de aristas de G es también impar.
1 respuesta
·
.
¡Hola Carolina Boni!
Comenzamos por un vértice, su orden es impar luego de el parten un numero impar de aristas. De los vértices a los que hemos llegado también parten un número impar de aristas, como una de ellas es la que venia del primer vértice, cada uno de los vértices nuevos añade un numero par de aristas nuevas (puede ser 0 también) luego entre todos añaden un número par de aristas nuevas que sumadas con las impares del primero hacen un número impar. Estas segundas aristas añaden nuevos vértices, vamos a ver que a cada uno de ellos solo se llega desde un vértice de los anteriores. Si se llegara desde dos tendríamos un ciclo formado por este vértice, los dos desde los que se llega y el vértice primero. Luego este conjunto de vértices nuevos solo tiene una arista de momento cada vértice y generará otras aristas nuevas en un número par, con lo cual la suma impar + par será impar y así pasara siempre en iteraciones sucesivas, nunca un vértice de los recientes nacerá con más de una arista porque se podría formar un ciclo entre el nuevo, dos que le preceden, y otros anteriores, en último caso el primer vértice siempre cerraría el ciclo si no se podía haber cerrado antes porque esta relacionado con todos. Luego en toda iteración se añade un número par de aristas nuevas a un número impar y el resultado es impar, así hasta que se acabe con todos los vértices. Como es conexa se acabará con ellos, ya que a todos se puede llegar desde el primero en un número finito de pasos.
Y eso es todo, saludos.
:
:
