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?
Diskret Matematikk: Bevis for antall bladnoder i et tre
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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:
* *
| /
* *
| /
*
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:
* *
| /
* *
| /
*