Planar Graph란, 평면 상에서 모든 Edge(또는 Vertice)가 서로 겹치지 않게 표현되는 Graph다. 노드 수가 4개 이하인 Complete Graph는 Planar Graph로 표현할 수 있지만, 노드 수가 5개 이상인 Complete Graph는 Planar Graph로 표현할 수 없다. 노드가 4개인 Complete Graph를 Planar Graph로 표현한 상태에서 노드 하나를 더 추가하면 Planar Graph를 만들 수 없음을 확인하라.
문제
다음 조건을 만족하는 그래프 G_n은 Planar Graph로 표현할 수 있을까?
- G_n의 노드는 노드 1, 노드 2, ..., 노드 n이다. (n은 자연수)
- 노드 x, 노드 y에 대해, x, y가 서로소이면 두 노드 사이에 Edge가 존재하지 않고, 서로소가 아니면 두 노드 사이에 Edge가 존재한다.
G_14는 Planar Graph로 표현할 수 있지만, G_15는 그렇지 않다. 먼저, 노드 2, 3, 5, 6, 10, 12, 15만을 고려하여 Planar Graph로 표현해보라. 그것은 앞서 언급된 '노드가 4개인 Complete Graph'와 같은 형태이므로 Planar Graph로 표현할 수 있다. 하지만 이 상태에서 노드 1을 추가하면, 그것은 '노드가 5개인 Complete Graph'와 같은 형태이므로 Planar Graph로 표현할 수 없다.
G_1 ~ G_13은 모두 G_14에서, 일부 노드와 Edge를 제거한 것이므로, 역시 Planar Graph로 표현할 수 있다. n > 15 인 모든 G_n은 G_15에서 노드와 Edge가 추가된 것이므로, 역시 Planar Graph로 표현할 수 없다.