Sbírka matematických úloh

Grafy bez čtyřcyklu

Úloha číslo: 3724

• Řešení

  Všimneme si, že graf incidence projektivní roviny nemůže obsahovat čtyřcyklus $a,P,b,Q$, protože by to znamenalo, že se přímky $P$ a $Q$ protínají ve dvou bodech.

  Je-li $G$ graf incidence projektivní roviny řádu $k$, je $|V_G|=n=2k^2+2k+2$ a $|E_G|=(k^2+k+1)(k+1)$. Protože $(k+1)^2>k^2+k+1$, dostaneme $|E_G|\ge \frac{n}2 \sqrt{\frac{n}2}=2^{-3/2}n^{3/2}$.