Matematické Fórum

Asi by bylo nutné podobný graf zkonstruovat nebo podrobněji popsat proč tento graf existuje. To, že napíšeš posloupnost čísel a prohlásíš, že je to skóre grafu, ještě nedokazuje, že takový graf existuje.

Třeba by bylo možné toto řešit indukcí: pro n=1 a n=2 vezmeme grafy bez hran. (Resp. pro korektnost indukce ještě vezmeme pro n=3 graf, u kterého jsou hranou spojeny právě dva libovolné vrcholy). Označme takto konstruované grafy na n vrcholech symbolem G(n). Konstruujme nyní pro n>3 graf G(n) tak, že vezmeme graf G(n-2), spojíme jeho všechny hrany s jedním novým vrcholem a druhému novému vrycholu necháme naopak stupeň 0 (nespojíme ho s žádným vrcholem). Tím jsme zvýšili počet vrcholů o 2, ale i počet různých stupňů také o 2 (stupeň 0 a n-2 nebude žádný vrchol z G(n-2) - poté co jsme ke každému jeho vrcholu přidali jednu hranu - mít: stačí indukcí ukázat, že v G(n) není žádný vrchol spojený se všemi ostatními vrcholy). Počet různých stupňů v G(n-2) - po přidání jedné hrany ke každému vrcholu - se však nezmění - stupeň každého vrcholu se zvětšil o 1. Tedy měl-li původní graf na n-2 vrcholech počet různých stupňů n-3 (dle indukce platí a pro n=2 a n=3 také), bude mít graf na n vrcholech počet různých stupňů n-1.

Protože jsem se zbytečně rozepsal, tak to shrnu: s grafu G na n-2 vrcholech vyrobím graf F na n vrcholech (má 2 nové vrcholy A a B) tak, že všechny vrcholy G spojím s A a vrchol B nespojím s žádným vrcholem.

Šlo by i rovnou použít tzv. věty o skóre + indukce na to, abychom ukázali, že pro sudá n je

skórem grafu, a pro lichá to je
.