====== سوال ۳ ======

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

  * [[سوال ۲|سوال قبل]]