Buenas.
Quisiera saber cómo hecer esa demostración: Sea d ≥ 2 un entero positivo dado. Probar que si un árbol tiene un vértice de grado d entonces tiene al menos d hojas.
Buenas.
Intuitivamente: supongamos por ejemplo que el árbol tiene un vértice de grado
. Entonces hay 3 aristas que salen de ese vértice. Cada una de esas 3 aristas debe terminar en una hoja, ya que de lo contrario el grafo tendría un ciclo, lo cual no es posible por ser árbol. Por la misma razón, las hojas en las que termina cada arista deben ser distintas entre sí. Esto implica que el árbol tiene al menos 3 hojas distintas.
Formalmente lo podés probar usando la expresión de la suma de grados de un grafo, y la relación entre cantidad de aristas y vértices de un árbol. Para esto te sugiero definir una variable
que represente la cantidad de hojas del árbol. Te gustaría probar que 
.
Intentalo y si no te sale preguntá de nuevo, o lo vemos en las consultas de esta semana.
Saludos.
Intuitivamente: supongamos por ejemplo que el árbol tiene un vértice de grado
. Entonces hay 3 aristas que salen de ese vértice. Cada una de esas 3 aristas debe terminar en una hoja, ya que de lo contrario el grafo tendría un ciclo, lo cual no es posible por ser árbol. Por la misma razón, las hojas en las que termina cada arista deben ser distintas entre sí. Esto implica que el árbol tiene al menos 3 hojas distintas.Formalmente lo podés probar usando la expresión de la suma de grados de un grafo, y la relación entre cantidad de aristas y vértices de un árbol. Para esto te sugiero definir una variable
que represente la cantidad de hojas del árbol. Te gustaría probar que .Intentalo y si no te sale preguntá de nuevo, o lo vemos en las consultas de esta semana.
Saludos.