Esercizio di dimostrazione su albero

[jacopo35]

L'esercizio è il seguente:

Sia T(V,E) un albero non orientato e sia k il numero dei vertici di grado maggiore o uguale
a 3. Dimostrare che l’albero T deve avere almeno k + 2 foglie.

La dimostrazione dovrebbe essere simile a quella fatta per questo esercizio:

Dimostrare la seguente affermazione. Se un albero ha un vertice di grado k, allora ha almeno k vertici di grado 1.

$\sum_{v in |V|} gr(v)$=$2|E|$ dove |V| è il numero di vertici, |E| è il numero di spigoli

$S={v in |V| : gr(v)=1}$ (i vertici di grado 1), $S sub V$

$gr(\bar v)=k$ (il vertice di grado k)

Si ha che:

$k+ |S|+ \sum_{v notin S, v!=\bar v} gr(v) >= k+ |S|+ 2*(|V|-|S|-1)$

ora $k+ |S|+ \sum_{v notin S, v!=\bar v} gr(v) = \sum_{v in |V|} gr(v) = 2|E|$ quindi:

$2|E| >= k+ |S|+ 2*(|V|-|S|-1)$

Sapendo inoltre che un albero con n vertici, ha n-1 spigolo, si ottiene

$2(|V|-1) >= k+ |S|+ 2|V| - 2|S| -2$

$0 >= k - |S|$ ovvero $|S|>=k$ cvd

Non chiedo tutta la dimostrazione, ma di fornire l'input.
Per esempio, allo stesso modo dell'esercizio appena fatto, io avrei definito l'insieme S dei vertici di grado>=3, e l'insieme T dei vertici di grado 2.

[adaBTTLS1]

provo a scrivere qualcosa in modo un po' informale.
n, numero dei vertici
n-1, numero di spigoli
2n-2, somma delle valenze (gradi dei vertici)
k, numero di vertici di grado 3
h, numero di vertici di grado 2
j, numero di vertici di grado 1 (foglie)

3k+2h+j=2n-2
k+h+j=n

2k+2h+2j-2=2n-2
3k+2h+j=2k+2h+2j-2

k-j=-2

j=k+2

spero di essere stata chiara. ciao.

[jacopo35]

Chiarissima.

Tenendo conto che i k vertici hanno grado >= 3:

k+h+j=n
2n-2=$a$k+2h+j (con $a$>=3)

2k+2h+2j-2=$a$k+2h+j
j=($a$-2)k+2

da cui si vede subito che se $a$>=3 -> j >= k+2