Miii-11.notebook
November 28, 2012
OOAOO|0/I1/I
J? =T
11 28-12:00
11 28-12:30
X- \eV= o •* WM . Is.!-7!
11 2H--\2Aii
11 28-12:54
-11 .notebook
November 28, 2012
Přeložíme si požadavek pravideínosti do vlastností příslušného grafu: chceme aby každý vrchol měl stejný stupeň cř>3a zároveň aby na hranici každé stěny byl stejný počet k > 3 vrcholů Označme n počet vrcholů, e počet hran a s počet stěn. Máme k dispozici jednak vztah provazující stupně vrcholů s poetem hran:
dn - 2e
a podobně počítáme počet hran. které ohraničují jednotlivé steny, a bereme v úvahu, že každá je hranící dvou stěn, tj.
2 e = ks
Eulerův vztah pak.ľfká-
Úpravou odtud dostáváme pro naše známé d a k vztah
lili     ^ A    h h
11 28-13:02
1   1 1
1 (x) -j> <K*1>
11 28-13:04
ti   in - lei
11 28-13:11
» K5 není rovinný; » K33 není rovinný;
* každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5;
• každý rovinný graf bez trojúhelníků obsahuje alespoň jeden vrchol stupně nejvýše 3.
11 28-13:1 /
11 28-13:15
11 28-13:37
Miii-11.notebook
November 28, 2012
11 28-13:35
3