생성수형도 개수

주어진 그래프는 10개의 꼭짓점을 가지고 있으므로 수형도가 되려면 변이 9개 필요하다. 그러므로 13개의 변 중 9개의 변을 택하면 된다. 여기서, 변 e는 반드시 택해져야 하므로 나머지 12개의 변 중 8개가 선택되어야 한다. 따라서 구하고자 하는 생성수형도의 개수는 ${} _{12} C _{8} -$ (4개의 변을 제거할 때, 성립하지 않는 경우의 수) 이다. 4개의 변을 제거하여 생성수형도가 되지 않는 경우는 제거하는 변의 개수에 따라 다음과 같이 분류할 수 있다. ㄱ) $A$에서 0개, $B$에서 4개 : ${} _{9} C _{4} = 126$ ㄴ) $A$에서 1개, $B$에서 3개 : $3 \times ( 7 + 7 + 7 + 6 + 6 + 10 ) = 129$ 변 4개의 변을 제거해야 한다. ㄷ) $A$에서 2개, $B$에서 2개 : $3 \times _{9} C _{2} = 108$ ㄹ) $A$에서 3개, $B$에서 1개 : $1 \times 9 = 9$ ㄱ), ㄴ), ㄷ), ㄹ) 에서의 총합은 372개이다 $\therefore _{12} C _{8} - 372 = 495 - 372 = 123$