matematikk.net

Hei, kan noen hjelpe meg med denne?

Let T be a tree with at least 2 vertices, and let k be the number of
vertices in T with degree at least 3. Prove that T has at least k+2 leaves

Hva er det beste? Bruke induksjonsbevis?

Induksjon funker greit. Gir den overordnede ideen her:

med k=0 har du et tree som ser ut som en v, og du har åpenbart 2 'leaves'. Hver gang du utvider treet med en vertex av grad 3 får du minst ett nytt blad (du mister et blad der den nye vertexen plugges på, men får to nye - altså i sum én til).

før, eks:

* *
| /
*


etter, eks:

* *
| /
* *
| /
*