در این قسمت 10 سوال وجود دارد
ثابت کنید مکمل یک گراف منتظم همچنان منتظم است.
جدول زیر را کامل کنید
| نام گراف | تعداد راس | تعداد یال | $\delta$ | $\Delta$ | $\chi$ |
|---|---|---|---|---|---|
| $P_n$ | n-1 | ||||
| $C_n$ | اگر n فرد باشد ۳ وگرنه ۲ | ||||
| $K_n$ | |||||
| $\overline{K_n}$ | |||||
| $K_{a,b,c}$ | |||||
| گراف پیترسن | |||||
| $Q_n$ | $2^n$ |
خانواده $O_{n,k,x}$ از گراف ها به این صورت تعریف می شوند که به ازای هر زیر مجموعه $k$ عضوی از مجموعه اعداد ${1..n}$ یک راس دارد و دو راس به هم یال دارند اگر و تنها اگر اشتراکشان $x$ عضوی باشد.
گراف جایگشت های $n$ تایی را به این صورت تعریف می کنیم که به ازای هر جایگشت یک راس در این گراف وجود دارد و
با استفاده از گراف های کامل (و نه جبر!) گزاره های زیر را ثابت کنید
یک گراف ساده جداقل چند راس نیاز دارد تا بتواند ۳۷۰۰ یال داشته باشد؟
مشخص کنید گراف های دو بخشی کاملی را که یک گراف کامل هستند.
مکمل گراف استار را چگونه میتوان توصیف کرد؟
ثابت کنید که اگر درجه هر راس یک گراف ساده دو باشد، گراف مورد انتظار اجتماعی از دور هاست.
ثابت کنید اگر درجه هر راس حداکثر دو باشد گراف مورد نظر اجتماعی از مسیر ها و دور هاست.