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|≥n2√n2=2−3/2n3/2.