Dato un albero (finito) $\mathcal{T}$, dimostrare che se non ci sono vertici con valenza $2$ in $\mathcal{T}$, allora il numero di foglie è maggiore del numero degli altri vertici.
Nota. Vabbè, tanto lo sapete. Comunque, un albero è un grafo connesso senza cicli e una foglia è un vertice di un albero con valenza $1$.
Albero, foglie (problema quasi noto)
Albero, foglie (problema quasi noto)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Re: Albero, foglie (problema quasi noto)
Allora, è abbastanza noto che un albero di $V$ vertici ha esattamente $V-1$ lati; ma con un double counting abbastanza standard sulla valenza totale del grafo (chiamato $f$ il numero di foglie) si ha
$$2(V-1)=\sum_{v} \deg(v)\Rightarrow 2(V-1)=f+\sum_{v\ne f} \deg(v)$$
Supponendo che non ci siano vertici di valenza $2$, al minimo ogni vertice che non è una foglia (sono $V-f$) avrà valenza $3$, da cui
$$2(V-1)=f+\sum_{v\ne f} \deg(v)\geq f+\sum_{v\ne f} 3= f+3(V-f)$$
Dunque, risolvendo la disequazione si ottiene
$$2f\geq V+2\Rightarrow f\geq \frac{V}{2}+1$$
Quindi le foglie sono sicuramente più della metà dei vertici totali e abbiamo dimostrato la tesi.
$$2(V-1)=\sum_{v} \deg(v)\Rightarrow 2(V-1)=f+\sum_{v\ne f} \deg(v)$$
Supponendo che non ci siano vertici di valenza $2$, al minimo ogni vertice che non è una foglia (sono $V-f$) avrà valenza $3$, da cui
$$2(V-1)=f+\sum_{v\ne f} \deg(v)\geq f+\sum_{v\ne f} 3= f+3(V-f)$$
Dunque, risolvendo la disequazione si ottiene
$$2f\geq V+2\Rightarrow f\geq \frac{V}{2}+1$$
Quindi le foglie sono sicuramente più della metà dei vertici totali e abbiamo dimostrato la tesi.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!