A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Megoldás. Az egyes csúcsokhoz rendelt számok csak attól függnek, hogy hány darab 2-essel jelölt él fut be ezekbe a csúcsokba. Ha db 2-es él fut be, akkor a csúcsra írt szám lesz. Ezért elég a 2-essel jelölt éleket tartalmazó gráfot vizsgálni. Ez is egy csúcsú egyszerű, de nem feltétlenül összefüggő gráf lesz. Ebben a gráfban minden csúcs fokszáma a halmazból kerül ki, de nem lehet egyszerre 0 fokszámú csúcs és fokszámú csúcs is, hiszen ha van fokszámú csúcs, akkor az minden más csúccsal össze van kötve egy-egy éllel, így nem lehet 0 fokszámú csúcs. Ezek szerint az darab fokszám legfeljebb -féle értéket vehet fel, így a skatulyaelv szerint lesz két megegyező fokszámú csúcs. Ez azt jelenti, hogy az eredeti gráfban lesz két csúcs, amibe ugyanannyi 2-essel jelölt él fut be, így ugyanannyi lesz a hozzájuk rendelt szám. Ezt akartuk belátni. |
|