La prueba de la teoría de grafos: grado máximo y el número de hojas.

Question

Tengo que demostrar que si $v$ es un vértice de grado máximo en un árbol y el grado de $v$$k$, entonces el árbol tiene al menos $k$ vértices de grado $1$.

Creo que puedo conseguir por que eso es cierto: Si $v$ $k$ a los vecinos, a continuación, estos pueden o no tener vecinos. Si se deja, entonces hemos terminado. Si no tiene vecinos, en algún momento vamos a llegar a las hojas, ya que el árbol es finito. Así que es obvio que el árbol tiene al menos $k$ vértices de grado $1$. Pero, ¿cómo puedo demostrarlo formalmente?

Answer 1

El caso de $k=1$ es trivial. Suponga que $k \ge 2$. Deje $u$ ser un vértice de grado $k$ - Lo $u$ no es una hoja.

Es bien conocido que $$\sum_{v \in V} deg v = 2E$$ en cada gráfico. También, $$E=V-1$$ en cada árbol. Así $$\sum_{v \in V} deg v = 2V - 2$$ Definir $L$ para el conjunto de las hojas de la gráfica. El grado de cada vértice de la hoja de al menos $2$, por lo que se deduce que (con un poco de abuso de notación)

$$\sum_{v \in V} deg v = deg u + \sum_{v \in L} deg v + \sum_{v \in V\(L \cup \{u\})} deg v \ge k + L + 2(V-L-1)$$

Así

$$2V -2 \ge k + 2V -L -2$$

y de ello se sigue que $L \ge k$.

Answer 2

Su razón intuitiva es muy correcto. Una manera de formalizar este sería tomar, para cada vecino de $v$, el más largo de la ruta que comienza en $v$ y pasa a través de ese vecino. Cada ruta debe terminar en una hoja, ya que si el último borde conduce a un vértice de grado más de $1$ podríamos tomar otro borde de ese vértice, que no puede ser parte de un ciclo, de modo que se crea una ruta más larga. Todas las $k$ deja encontrado en esta forma son diferentes: rutas para salir de la $v$ en direcciones diferentes no pueden tener el mismo final, ya que requeriría de un ciclo.

Answer 3

Si $v$ es un vértice de grado $k$ en el árbol de $T,$ $T-v$ es un bosque de $k$ árboles $T_1,\dots,T_k,$ uno para cada vecino de $v$ $T.$ Si $T_i$ se compone de un solo vértice, luego de que el vértice era una hoja en $T.$ Si $T_i$ contiene más de un vértice, entonces $T_i$ tiene al menos dos hojas; al menos uno de ellos no era un vecino de $v,$, por lo que también fue una hoja en $T.$