2005학년도 대학수학능력시험 예비평가 수리 영역 가형 이산수학 28번

<증명>

꼭지점이 $n$개 있고 차수가 1인 꼭지점이 2개 있는 수형도 $T$를 택하자. 이때, $T$의 각 꼭지점의 차수를 $d_1,\ d_2,\ \cdots,\ d_n$이라 하자.

$T$의 변의 개수가 $\boxed{\text{(가)}}$이므로 그래프의 차수의 합과 변의 개수 사이의 관계로부터 다음을 얻는다.

만약 어떤 $j$에 대하여 $d_j\ge3$이라 가정하면 다음이 성립한다.

(다)는 (나)에 모순이므로 차수가 1이 아닌 꼭지점의 차수는 2이다.