생성수형도 개수

주어진 그래프에서 생성수형도를 만들때 변을 제거한 그래프가 연결된 그래프이어야 하므로 $2$개의 변을 제거해야 한다. 이때, 구하는 생성수형도의 개수는 ($7$개의 변 중 두 개의 변을 제거하는 경우의 수) -(두 개의 변을 제거해도 수형도가 되지 않는 경우의 수)이다. (ⅰ) $7$개의 변 중 제거할 두 개의 변을 선택하는 경우 $\displaystyle {} _{7} C _{2} = \frac{7 \times 6}{2} = 21$(개) (ⅱ) 두 개의 변을 제거해도 수형도가 되지 않는 경우 변 $xy , xu , uv$ 중 두 변을 제거하는 경우와 변 $yz , zw , vw$ 중 두 변을 제거하는 경우이므로 $2 \times _{3} C _{2} = 6$(개) 따라서 구하는 생성수형도의 개수는 $21 - 6 = 15$(개) [참고] 생성수형도란 연결된 그래프에서 변을 삭제하여 얻어지는 수형도를 말한다. [별해] 생성수행도를 그려보면 다음과 같다.

따라서 서로 다른 생성수형도의 개수는 $15$개이다.