گراف ساده ‎$G$‎ را در نظر بگیرید که ماتریس مجاورت آن ‎$A$‎ است . ‎$G$‎ را خوب می‌نامیم اگر و تنها اگر عددی طبیعی مانند ‎$k$‎ موجود باشد که ‎$A^k$‎ ماتریسی باشد که همه‌ی درایه‌هایش ناصفر است. (راهنمایی: به ارتباط درایه‌های ‎$A^k$‎ با گشت‌های به طول ‎$k$‎ در گراف توجه کنید‎.)

1. شرط لازم و کافی برای خوب بودن یک گراف معرفی کنید و ادعای خود را ثابت کنید‎.‎
2. ثابت کنید اگر ‎ $G$‌‎گراف ‎$n$‎ راسی و خوب باشد، عدد طبیعی ‎$k<2n$‎ وجود دارد که همه‌ی درایه‌های ‎$A^k$‎ ناصفر باشند‎.

• سوال قبل