Trojúhelník a čtyřcyklus
Úloha číslo: 3787
Hrany úplného grafu \(K_n\) jsou obarveny červeně a modře. Dokažte, že v tomto grafu najdeme buď modrý trojúhelník nebo červený čtyřcyklus pro
Varianta
\(n=9\).
Řešení
Zvolíme libovolný vrchol \(u\). Buď z \(u\) vedou alespoň čtyři modré hrany nebo alespoň pět červených.
V prvním případě, nemají li tyto modré hrany být doplněny na modrý trojúhelník musíme vždy doplňovat červenou hranou, čímž vytvoříme červený \(K_4\), který obsahuje \(C_4\).
Ve druhém případě nesmíme mezi vrcholy jež sousedí s \(u\) přes červené hrany vytvořit červenou cestu délky dvě. Červené hrany proto tvoří na těchto pěti vrcholech párování, což je graf s alespoň třemi komponentami. Vybereme-li z každé komponenty jeden vrchol, dostaneme modrý trojúhelník.
Varianta
\(n=8\).
Řešení
Postupujeme podobně jako v předchozím případě. Pokud nemá nastat ani jedna ze situací popsaná v předchozí variantě, znamená to, že do \(u\) vedou tři modré hrany, jejichž opačné konce \(M=\{m_1,m_2,m_3\}\) indukují červený trojúhelník, a další čtyři červené hrany, jejichž opačné konce \(C=\{c_1,…,c_4\}\) indukují modrý čtyřcyklus s červenými úhlopříčkami.
Pokud by z \(c_1\) vedla nějaká červená hrana do množiny \(M\), musely by všechny hrany vedoucí z \(c_3\) do \(M\) být modré, abychom nedostali červený \(C_4\) (dva případy: buď procházející \(c_1,u,c_3\) a společným "červeným" sousedem \(c_1\) a \(c_3\) nebo procházející \(c_1,c_3\) a jejich dvěma sousedy v \(M\)). Podobně buď z \(c_2\) anebo z \(c_4\) vedou do \(M\) jen modré hrany. Tímto způsobem však získáme modrý trojúhelník ze dvou vrcholů z \(C\) a jednoho z \(M\).