در این قسمت 12 سوال وجود دارد
ثابت کنید در هر گراف که $ \delta \ge 2 $ باشد مسیری با $ \delta $ یال و دوری با حداقل $ \delta + 1 $ راس وجود دارد.
ثابت کنید در هر گرافی که $ \delta \ge 3 $ باشد دور زوج (دوری که زوج راس داشته باشد) وجود دارد.
ثابت کنید هر گرافی با n یال دور دارد.
ثابت کنید اگر از راس a به راس b و از راس b به راس c مسیری وجود داشته باشد، از راس a به c نیز مسیر وجود دارد.
فرض کنید $G$ یک گراف با کمر حداقل 5 و k-منتظم باشد. ثابت کنید این گراف حداقل $k^2+1$ راس دارد. برای $k=2,3$ یک مثال با دقیقا $k^2+1$ راس بزنید.
گراف های فرد خانواده ای از گراف ها هستند. گراف $O_k$ به این صورت تعریف می شود که به ازای هر زیر مجموعه $k$ عضوی از مجموعه ${ 1 .. 2k+1 }$ یک راس دارد و دو راس به هم یال دارند اگر و تنها اگر مجموعه هایشان مجزا باشند. می توانید بررسی کنید که $O_2$ همان گراف پیترسن است. ثابت کنید که کمر گراف $O_k$ برابر ۶ است وقتی که $k \ge 3$ باشد.
تعداد دور های به طول $n$ در گراف $K_n$ و دور های به طول $2n$ در گراف $K_{n,n}$ را بشمارید. دقت کنیذ که دو دور متمایز در نظر گرفته می شوند اگر و تنها اگر یال هایشان متفاوت باشد؛ یعنی حداقل یک یال در یکی باشد و در دیگری نباشد.
تعداد دور های به طول ۶ گراف پیترسن را بشمارید.
ثابت کنید گراف پیترسون دور به طول ۷ ندارد.
به ازای هر $k \ge 2$ و $g \ge 2$ ثابت کنید گرافی k منتظم با کمر g وجود دارد.
دور های به طول 6 در گراف $Q_3$ را بشمارید. ثابت کنید که هر دور به طول 6 در گراف $Q_k$ درون یک زیر مکعب سه بعدی می افتد. به کمک این دو مطلب، تعداد دور های به طول 6 در $Q_k$ را بشمارید.