Cada árbol tiene al menos △ (G) hojas

Question

Yo quiero probar la declaración de

Cada árbol tiene al menos △(G) hojas

donde △(G) es el más alto grado de los vértices. He visto una prueba de esta afirmación, pero parecía demasiado complicado, así que quería construir una sencilla prueba.

Pensé en una prueba que va como sigue: Si dejamos $v$ ser este vértice de mayor grado. Por lo que v tiene △(G) de los vecinos, y como G es un árbol, si seguimos un camino que comienza en v y va a través de cada uno de estos vecinos, que finalmente encontrar una hoja, por lo tanto tenemos △(G) hojas.

Esta es una prueba válida? No estoy completamente seguro de cómo formular mi idea, pero, básicamente, implica partir de $v$ y, a continuación, ir a un vecino y siguiendo un camino hasta encontrar una hoja, que sabemos existen en la ruta, finalmente, como G es un árbol, y tenemos al menos △(G) tales caminos.

Answer 1

"finalmente encontramos una hoja" es cierto, pero tiene un pequeño argumento, que implica el hecho de que no tenemos ciclos. Tal vez esto ya es una propuesta en el texto que estás usando, así que usted puede hacer referencia a en ese caso.

Sostienen también que los diferentes caminos vértice discontinuas (excepto el vértice de partida $v$) porque de lo contrario otra vez tendríamos un ciclo. Es mejor hacerlo explícito. En particular entonces los vértices hojas son distintos.