트리는 평면 그래프의 일종이죠. (평면 위의 점들을 이어서 나타낼 수 있으니까) 평면 그래프에서 최대 채색 수가 4라는 것은 "4색정리"라는 유명한 정리로, 이미 증명되었습니다.

https://ko.wikipedia.org/wiki/%ED%8F%89%EB%A9%B4_%...

https://ko.wikipedia.org/wiki/4%EC%83%89%EC%A0%95%...

https://en.wikipedia.org/wiki/Four_color_theorem

최대 채색수라고 하니 말이 좀 이상한데 4가지 색만 써서 이웃한 정점끼리 모두 색이 다르도록 칠할 수 있다는 뜻입니다.

5개의 색을 사용했을 때 더 이득인 상황이 발생할 수도 있지 않나요?

네 발생할 수 있습니다. 그러한 상황을 필요로 하는 테스트 데이터도 얼마 전 추가되었습니다.

@kdh9949 사람들이 자꾸 이 글 때문에 틀리는 듯 반성좀;

내용에 대해서 첨언을 하겠습니다. 트리를 4색으로 칠할 수 있는 것은 사실입니다. 더 나아가서, 트리는 이분 그래프의 일종이기에 2색으로도 칠할 수 있습니다. 

하지만, 이러한 사실과 문제의 상황은 크게 관련이 없어 보입니다. 문제는 최소의 비용을 묻지, 최소의 색깔을 묻는 게 아니니까요. 2색으로 트리를 칠하면 예제 조차도 안나오고, 4색으로 트리를 칠했을 때의 반례 데이터가 제시되었으니, 다른 풀이를 생각하는 것이 나아 보입니다. 

ㅠㅠ

앞으로는 푼 문제에만 댓글 달겠습니다...