Có 5 hòn đảo được vẽ như 5 điểm phân biệt, trong đó có đúng hai hòn đảo được nối với nhau bởi một cây cầu, được vẽ như một đoạn thẳng (h.8.28). Hỏi phải xây thêm ít nhất bao nhiêu cây cầu nối các hòn đảo để có thể đi qua lại giữa hai hòn đảo tuỳ ý thông qua các cây cầu đó?
Kẻ tất các các đoạn thẳng với đầu mút lần lượt là A, B, C, D, E.
Các đoạn thẳng trùng nhau thì không đếm.
Advertisements (Quảng cáo)
Đầu mút A: có 4 đoạn thẳng AB, AC, AD, AE.
Đầu mút B: có 3 đoạn thẳng BC, BD, BE (BA trùng với AB nên không đếm).
Đầu mút C: có 2 đoạn thẳng CD, CE (CA trùng AC, CB trùng BC).
Đầu mút D: có 1 đoạn thẳng DE (DA trùng AD, DB trùng BD, DC trùng CD)
Đầu mút E: không thêm đoạn thẳng nào (vì EA trùng AE, EB trùng BE, EC trùng CE, ED trùng DE ở trên).
Do đó cần ít nhất 4+3+2+1=10 cây cầu nối hai hòn đảo tùy ý.
Vậy cần phải xây thêm 10 - 1 = 9 cây cầu.