그래프의 성질

ㄱ. (거짓) 그래프 $G$는 변이 꼭짓점에서만 만나게 평면 위에 다시 그릴 수 없으므로 평면그래프가 아니다. ㄴ. (참) 그래프 $G$에서 해밀턴회로를 찾아보면 $\mathrm{A} \rightarrow E \rightarrow F \rightarrow C \rightarrow B \rightarrow D \rightarrow A$가 있으므로 해밀턴회로를 갖는다. ㄷ. (참)

위의 그래프 $G$에서 $\mathrm{A} , B , F$에 $1$가지 색, $\mathrm{D} , E , C$에 또 다른 $1$가지 색을 사용하면 되므로 꼭짓점을 적절하게 색칠할 수 있는 최소의 색의 수는 $2$이다. 따라서, 옳은 것은 ㄴ, ㄷ이다.