پنج شهر D،C،B،A و E را در نظر بگیرید. قراراست به هر کدام از شهرهای B،A و C دو جاده و به هر یک از شهرهای D و E یک جاده متصل باشد.
به چند طریق میتوان این شهرها را با تعداد لازم جاده به هم وصل کرد به طوری که به هر شهر به تعداد فوق جاده متصل باشد و نیز از هر شهر بتوان با حرکت روی جادهها به تمام شهرهای دیگر رفت؟
پاسخ
گزینه (۳) درست است.
شهر متصل به D یکی از شهرهای B،A یا C میباشد زیرا اگر D به E متصل باشد آنگاه شهر D به غیر از E به هیچ شهر دیگری مسیر نخواهد داشت. به همین صورت E نیز به یکی از شهرهای B،A یا C (به غیر از شهری که D به آن متصل است) وصل خواهد بود. بنابراین تعداد جوابهای ممکن برابر 3×2 یعنی ۶ خواهد بود.