Filtr seznamu úloh?

Zvolte požadované hodnoty úrovní a požadované štítky. V obsahu budou zobrazeny pouze úlohy mající jednu ze zvolených úrovní každé škály a alespoň jeden štítek. Pokud chcete filtrovat pouze podle některých škál nebo jen podle štítků, nechte ostatní skupiny prázdné.

Škály

Obtížnost

Štítky

Typ úlohy
«
«
«

Grafy bez čtyřcyklu

Úloha číslo: 3724

Dokažte, že pro nekonečně mnoho různých n existují grafy na n vrcholech s Ω(n3/2) hranami, které neobsahují jako podgraf čtyřcyklus (C4). Ke konstrukci můžete elegantně využít konečné projektivní roviny.

  • Ř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 |VG|=n=2k2+2k+2 a |EG|=(k2+k+1)(k+1). Protože (k+1)2>k2+k+1, dostaneme |EG|n2n2=23/2n3/2.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze