6주차 확인학습 8번 채색수

[소년일보]

일단 저런식으로 숫자를 대입해봐서 5채색 가능까진 알아냈는데

이게 최소라는 보장은 어떻게 할수있나요?

빨간펜으로 쓴 숫자는 숫자에 번호를 부여한 거에요 1번색 2번색 이런식으로요

[박정환]

C_7의 두 점과 K_3,1에서의 어떤 두 점을 선택하면 k_4와 동형인 부분그래프이므로 4개 이상이어야 합니다.
또한 C_7의 선택된 두점과 인접한 C_7의 꼭짓점 중 하나는 반드시 4개의 색과는 다른 색이어야 하기 때문입니다.