평면그래프

평평한 땅 위에 집 세 채와 수도국, 전력소, 가스소가 있다. 각 집을 세 시설과 모두 관으로 이어야 하는데, 관끼리는 겹치거나 교차하면 안 되고 땅 밖으로 우회할 수도 없다. 관은 모두 9개인데, 아무리 구불구불하게 돌려 보아도 마지막 하나가 꼭 다른 관을 가로지른다. 정말 불가능한 것일까? 정육면체의 꼭짓점과 모서리를 평면에 펼쳐 그리면 선이 겹치지 않는데, 둘은 무엇이 다를까?

4.4.1오일러 공식

변끼리 꼭짓점이 아닌 곳에서 만나지 않도록 평면에 그릴 수 있는 그래프를 평면그래프라 한다. 평면그래프를 그리면 변들이 평면을 여러 영역으로 나누는데, 그 영역을 면이라 하고 바깥의 끝없는 영역도 하나의 면으로 센다. 연결된 평면그래프에서는 꼭짓점 수 \(v\), 변 수 \(e\), 면 수 \(f\)가 늘 \(v - e + f = 2\)를 만족한다. 변 하나를 더하면 면이 하나 늘거나 꼭짓점이 하나 늘어, \(v - e + f\)는 바뀌지 않기 때문이다. 꼭짓점 하나에서 출발하면 \(1 - 0 + 1 = 2\)이다.

단순그래프에서 각 면은 적어도 세 개의 변으로 둘러싸이고, 각 변은 많아야 두 면의 경계가 된다. 그래서 면의 경계를 이루는 변을 모두 세면 \(3f \le 2e\)이다. 이것을 오일러 공식에 넣으면 \(e \le 3v - 6\)이 된다. 삼각형이 없으면 각 면이 적어도 네 변으로 둘러싸여 \(4f \le 2e\)이고, 같은 방법으로 \(e \le 2v - 4\)가 된다. 이 부등식을 어기는 그래프는 아무리 잘 그려도 선이 겹친다.¹

4.4.2정다면체가 다섯 가지뿐인 까닭

볼록한 다면체의 꼭짓점과 모서리는 한 면을 펼쳐 바깥 면으로 삼으면 평면그래프로 그릴 수 있다. 그래서 다면체에서도 꼭짓점 수에서 모서리 수를 빼고 면 수를 더하면 2이다. 이 공식에 모든 면이 같은 정다각형이고 각 꼭짓점에 같은 수의 면이 모인다는 조건을 넣으면, 가능한 경우가 정사면체, 정육면체, 정팔면체, 정십이면체, 정이십면체의 다섯 가지뿐임을 보일 수 있다.

4.4.3예제 풀이

\(K_{3,3}\)은 꼭짓점 6개, 변 9개이다. 변은 늘 집과 시설 사이에만 있으므로 집끼리나 시설끼리는 이어져 있지 않고, 그래서 삼각형이 없다. 만약 평면그래프라면 \(e \le 2v - 4 = 8\)이어야 하는데 변이 9개이므로 모순이다. 오일러 공식으로 보면 평면그래프일 때 면이 \(f = 2 - 6 + 9 = 5\)개여야 하는데, 각 면이 네 변 이상으로 둘러싸이면 \(4\times5 = 20 \le 2\times9 = 18\)이 되어 모순이다. 그래서 관 하나는 반드시 다른 관을 가로지른다.

정육면체는 꼭짓점 8개, 모서리 12개, 면 6개이므로 \(8 - 12 + 6 = 2\)이다. 평면에 펼친 그림에서도 안쪽 면 5개와 바깥 면 1개를 합해 면이 6개이다. 즉 평면그래프는 오일러 공식 \(v - e + f = 2\)를 만족하고, 그 결과인 변의 개수의 상한을 어기는 그래프는 평면에 선이 겹치지 않게 그릴 수 없다.

아래 탐구 카드에서 엉킨 그래프를 선이 겹치지 않게 펴 보고, 평면그래프에서 점, 선, 면의 수 사이의 관계를 확인해 보자.

1. 1930년 폴란드의 쿠라토프스키는 어떤 그래프가 평면그래프가 아닐 필요충분조건이 \(K_5\)나 \(K_{3,3}\)을 변을 나누어 늘인 모양을 품는 것임을 증명했다. 전자 회로 기판을 설계할 때 배선이 겹치지 않게 하는 데 이 이론이 쓰인다.