از دو پرسش زیر یکی را به دل‌خواه انتخاب کرده و پاسخ دهید:

۱) در گراف ساده‌ی $G$، دور به طول ۳ و دور به طول ۴ وجود ندارد. ثابت کنید:

$$m(G) \leq \frac{n \sqrt{n-1}}{2}$$

۲) فرض کنید $H$ گرافی است که مجموعه‌ی رئوس آن به صورت

$$V(H)=\{(a,b)|0<a<p,0\leq b<p\}$$

است و هم‌چنین از راس $(a,b)$ به راس $(c,d)$ یال وجود دارد، اگر و تنها اگر $ac\equiv b+d (mod \quad p)$ باشد. ثابت کنید گراف $H$ دور به طول ۴ ندارد و تعداد یال‌های آن از $\theta (n \sqrt{n})$ است.

• سوال بعد