생성수형도 개수

주어진 그래프의 꼭짓점의 개수가 $7$이므로 생성수형도의 변의 개수는 $6$이어야 한다. 그런데 주어진 그래프의 변의 개수는 $9$이므로 $3$개를 삭제해야 한다. 따라서 $9$개의 변 중 삭제할 $3$개의 변을 택하는 경우의 수는 $\displaystyle _{9} C _{3} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84$ (개) 그런데, 생성수형도에는 회로가 없어야 하므로 위의 $84$개의 그래프 중에서 회로가 있는 그래프를 제외해야 한다. (i) 다음 그림과 같이 맨 바깥쪽에 회로가 생기는 경우

$_{6} C _{3} = 20$ (개) (ⅱ) 다음 그림과 같이 맨 바깥쪽의 변 중 한 개만 남아서 회로가 생기는 경우

$3 \times _{4} C _{3} = 12$ (개) (ⅲ) 다음 그림과 같이 맨 바깥쪽의 변 중 두 개가 남아서 회로가 생기는 경우

$3 \times _{3} C _{3} = 3$(개) 이상에서 구하는 생성수형도의 총 개수는 $84 - ( 20 + 12 + 3 ) = 49$(개) [다른 풀이] 다음과 같이 직접 생성수형도의 개수를 구할 수도 있다. (i) 맨 바깥쪽의 변을 모두 삭제하는 경우

$_{3} C _{3} =$1 (개) (ⅱ) 맨 바깥쪽의 변 중 두 개를 삭제하는 경우

$_{3} C _{2} \times$$_{4} C _{1} = 12$ (개) (ⅲ) 맨 바깥쪽의 변 중 한 개를 삭제하는 경우

$_{3} C _{1} \times _{3} C _{1} \times 2 \times 2 = 36$ (개) 이상에서 구하는 생성수형도의 총 개수는 $1 + 12 + 36 = 49$ (개)