Trojúhelník v grafu s šesti vrcholy

Úloha číslo: 3657

Nechť \(G\) je graf s šesti vrcholy. Dokažte, že buď obsahuje trojúhelník, nebo indukovanou nezávislou množinu na třech vrcholech.

  • Řešení

    Zvolme libovolný vrchol \(v\). Rozborem případů ověříme, že nastane alespoň jedna z možností:

    • Vrchol \(v\) má stupeň alespoň tři a něteří z jeho sousedů jsou spojeny hranou. Potom obsahuje trojúhelník.
    • Vrchol \(v\) má stupeň alespoň tři a žádní z jeho sousedů nejsou spojeny hranou. Potom tito sousedé tvoří nezávislou množinu velikosti alespoň tři.
    • Vrchol \(v\) má stupeň nejvýše dva a něteří z jeho nesousedů nejsou spojeny hranou. Potom obsahuje nezávislou množinu velikosti tři.
    • Vrchol \(v\) má stupeň nejvýše dva a všichni z jeho nesousedů jsou spojeny hranou. Potom tito nesousedé tvoří úplný graf na alespoň třech vrcholech a v něm i trojúhelník.
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze