سلام
برای داشتن قطری با طول کمتر کافیه تا جایی که میتوانیم رئوس را به هم نزدیکتر کنیم مثلا یک راس مرکزی فرض کنیم و ۹۹ راس دیگر را دور ان قرار دهیم که هر کدام با یک یال به راس مرکزی وصل می شوندکه ۹۹ تا یال نیاز است و باید یک یال دیگر هم اضافه کنیم که اگر گراف را طبق معمول ساده فرض کنیم مجبوریم دو راس از ۹۹ راس اطراف راس مرکزی را انتخاب کنیم مثلا دو راس به نام های aو b در این حالت قطر گراف ۳ خواهد بود چرا که دو حالت داریم یا از یال ۱۰۰ یعنی (a,b ) استفاده نکنیم که طولانی ترین مسیر های مابه طول ۲ می شوند و اگر استفاده کنیم ۳ می شوند مثلا فاصله از a به یکی از راس های بجز b می شود ۳ مثلا مسیر ازa بهb و از b به مرکز و از مرکز به راس دیگر.
برای داشتن قطر حداکثر یک مسیر ساده با ۱۰۰ راس و ۹۹ تا یال را در نظر بگیرید که فاصله راس اول از اخر ۹۹ میشه یال ۱۰۰ هم می توانیم به دلخواه بین دوراس قرار دهیم که تاثیر ندارد چرا که باز دو حالت دارد یا انتخاب نمی شود یا می شود در حالت انتخاب نشدن طول طولانی ترین مسیر ها۹۹ می شود و در حالت انتخاب شدن اگر دو راس مجاور را به هم وصل کرده باشد که تاثیری ندارد و طول همچنان ۹۹ است و اگر دو راس غیر مجاور را وصل کند و استفاده هم بشه که طول مسیر را کم می کند پس:
[tex]99-3=96[/tex]
گزینه ی ۴