グラフを利用する場合の数の問題

算数にチャレンジ第408回

各島を正五角形の頂点に配置し、対角線と辺のどれを結ぶか考える。
すべての橋のかけ方は10C4=210通りある。
条件を満たさないものは、2-3,1-4の状態で島が孤立するもので、5C4・6C2=75通り,5c3=10通りある。
よって、答えは210-75-10=125通りとなる。