확률과 통계순열과 조합수능 기출기본 문제 (3점 중반)
채색수와 수형도 반례
문제
다음 명제의 반례가 되는 그래프는? [3점]
꼭지점을 적절하게 색칠하는 데 필요한 최소색의 수가 이면 그 그래프는 수형도이다.
①
②
③
④
⑤
정답 보기
④
자료 내려받기
아직 올라온 파일이 없습니다.
해설
반례는 꼭지점을 적절하게 색칠하는 데 필요한 최소의 색의 수가 2이지만 수형도는 아닌 것이다. 수형도는 회로를 갖지 않는 연결된 그래프이므로 보기 중 수형도가 아닌 것은③, ④, ⑤이다. 이 중 ③과 ⑤는 꼭지점을 색칠하는데 필요한 최소의 색수는 3개이고 ④는 2개이므로 반례로 알맞은 것은 ④이다.