Legyenek d1, d2, . , dn olyan pozitív egészek, melyek összege 2n − 2. Bizonyítsuk be, hogy van olyan fagráf, melynek ezek a fokszámai?

Nemcsak, hogy fagráfot, hanem Hamilton-utat kapunk.

Ha ezek a fokszámok n≥2-re:

d1=1

d2=2

d3=2

.

.

.

d(n-2)=2

d(n-1)=2

dn=1

Ezek összesen 2(n-2)+1*2=2n-4+2=2n-2.

Lehet, hogy van másik elrendezés is, de azt nem kérdezte, csak azt, hogy van-e ilyen fagráf. Mivel én találtam, ezért itt munkám bevégeztetett.

Első: nem csak az általad megadott konkrét (d1,...,dn) sorozatra, hanem tetszőleges olyanra, aminek az összege 2n-1, be kell látni az állítást.

Ez teljes indukcióval történhet.

n=2-re triviális, mert abban az esetben a feltételnek csak a d1=d2=1 sorozat felel meg.

Tegyük fel, hogy minden n-nél kisebb k esetén igaz az állítás: ha d1, ... ,dk összege 2k-2, akkor létezik a megfelelő fagráf. Belátjuk, hogy ekkor n-re is igaz.

Adjuk meg a d1,...,dn sorozatot. Biztos, hogy az elemei között szerepel az 1-es, hiszen az elemek összege kisebb kell, hogy legyen, mint 2n. Legyen d1=1.

Tekintsük a

d2,...,dn-1

n-1 tagú sorozatot. Ennek eleminek összege

d2+...+dn-1=(d1+d2+...+dn)-d1-1=(2n-2)-1-1=2(n-1)-2.

Tehát alkalmazva az indukciós feltételt, van olyan fagráf, amelynek a fokszámai d2,...,dn-1.

Az utolsó csúcsból indítsunk ki még egy élt, ami egy 1 fokú csúcsba fut! Az így kapott gráf éppen megfelel a feltételnek: a dn-1 fokú csúcs fokszáma 1-el nőtt, valamint keletkezett egy d1=1 fokú új csúcs.

Az ilyen feladatot úgy kell értelmezni, hogy BÁRMILYEN d1, d2, ... szám n-esre teljesül.

Akkor lenne igazad, ha úgy fogalmaz a feladat, hogy adjunk meg d1, d2, ... számokat...

Így már érthető. Félreértettem a kérdést.

Elnézést! :)