세 개의 노드를 가진 무방향 완전 그래프의 신장 트리(spanning … | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지

세 정점 무방향 완전 그래프의 신장 트리는 3가지이다.
신장 트리는 정점 3개를 간선 2개로 잇으므로, 간선 3개 중 하나를 빼는 경우의 수만큼 생긴다. 케일리 공식으로도 $n^{n-2}=3^{1}=3$ 이다.
1가지: 어느 간선을 빼도 서로 다른 트리가 되므로 하나뿐일 수 없다.
2가지: 뺄 수 있는 간선 후보가 3개이므로 부족하다.
4가지: 간선 3개 중 2개를 고르는 경우는 $\binom{3}{2}=3$ 을 넘을 수 없다.