Sbírka matematických úloh

Vrcholy nízkého stupně

Úloha číslo: 4317

• Varianta: Malý poměr

  Nejvýše \(1/100\) z celkového počtu vrcholů má stupeň menší než 6.

• Řešení

  Hledané grafy budou trojúhelníkové sítě: \(V=\{1,\ldots,n\}\times \{1,\ldots,n\}\), vrchol \((i,j)\) spojíme hranami s vrcholy \((i+1,j)\), \((i,j+1)\) a \((i+1,j+1)\).

  Všechny vnitřní vrcholy mřížky budou mít stupeň 6, vrcholy na okrajích menší. Teď si zbývá uvědomit, že všech vrcholů je řádově \(n^2\), zatímco vrcholů na okraji řádově \(n\). Jejich poměr tedy konverguje k nule, takže pro dost velké \(n\) bude menší než požadovaná \(1/100\).

• Varianta: Malý počet

  Nejvýše 6 vrcholů má stupeň menší než 6.

• Řešení

  Vezmeme konvexní čtyřstěn a jeho stěny vyplníme trojúhelníkovou sítí (rovnostranný trojúhelník rozdělíme na 4 shodné rovnostranné trojúhelníky a každý z nich rozdělujeme rekurzivně dál).

  Jaké vlastnosti tento graf má? Počet vrcholů může být libovolně vysoký, stačí rozdělovat stěny dostatečně dlouho. Vnitřní vrcholy trojúhelníkové sítě mají stupeň 6, vrcholy na hranách čtyřstěnu také, pouze 4 původním vrcholům čtyřstěnu zůstane stupeň 4.