سوال ۹

گزینه (۲) درست است.

فرض کنید جواب مسئله مربوط به درخت $T$ باشد. از روی $T$، درخت $T'$ را این گونه بسازید:

هر درخت ۷ راسی را معادل یک راس در نظر بگیرید و اگر بین دو راس از دو درخت در $T$ یالی بود، بین دو راس متناظر آن دو در $T'$ یک یال بگذارید. حال دو برگ از $T'$ را در نظر بگیرید. فرض کنید این دو برگ معادل دو درخت $T_1،T_2$ از $T$ باشند. فرض کنید رئوسی از $T_1$ و $T_2$ که به بیرون از این دو درخت یال دارند، به ترتیب $t_1$ و $t_2$ باشند (چون $T_1$ و $T_2$ برگ هستند این راس یکتاست). چون $T_1$ و $T_2$ درخت‌های ۷ راسی هستند رئوسی مانند $t'_1$ و $t'_2$ وجود دارند که $d_T(t_1,t'_1)\geq 3$ و $d_{T_{2}}(t_2,t'_2)\geq 3$. حال به وضوح می‌توان دید که $d_T(t'_1,t'_2)\geq 8$. پس قطر $T$ حداقل 8 است. حال اگر $T'$ را یک گراف ستاره ای در نظر بگیریم و به ازای هر یال مانند $T_1T_2$ در $T'$، مرکز درخت $T_1$ را به مرکز درخت $T_2$ در $T$ متصل کنیم. با توجه به این‌که شعاع هر گراف ۷ راسی حداکثر ۳ است، قطر گراف حاصل ۸ می‌شود. پس پاسخ مسئله برابر ۸ است.

شعاع گراف $G$ برابر است با: $min_{u\in V(G)} \{max_{w\in V(G)} d(u,w)\}$.