어떤 지도에서는 경계가 서로 닿아 있는 지역을 서로 다른 색으로 칠하여 경계를 구별하고 있다. 지도를 색칠하는 데 필요한 최소 색의 수를 구하기 위하여 그래프 색칠하기를 이용하려고 한다. 최소 색의 수와 그래프에 대한 의 설명에서 항상 옳은 것을 모두 고른 것은? [4점] ㄱ. 최소 색의 수가 2 이면 그래프는 수형도이다. ㄴ. 최소 색의 수가 3 이면 그래프는 한 개 이상의 회로를 갖는다. ㄷ. 최소 색의 수가 4 이면 그래프의 각 꼭짓점은 어떤 회로가 지난다.

초록띠 5기출문제

2007학년도 대학수학능력시험 6월 모의평가 수리 영역 가형 이산수학 29번

어떤 지도에서는 경계가 서로 닿아 있는 지역을 서로 다른 색으로 칠하여 경계를 구별하고 있다. 지도를 색칠하는 데 필요한 최소 색의 수를 구하기 위하여 그래프 색칠하기를 이용하려고 한다. 최소 색의 수와 그래프에 대한 <보기>의 설명에서 항상 옳은 것을 모두 고른 것은? [4점]

ㄱ. 최소 색의 수가 $2$ 이면 그래프는 수형도이다.

ㄴ. 최소 색의 수가 $3$ 이면 그래프는 한 개 이상의 회로를 갖는다.

ㄷ. 최소 색의 수가 $4$ 이면 그래프의 각 꼭짓점은 어떤 회로가 지난다.