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.