PART II — 구조
지하철 노선도, 회로 기판, 다이아몬드의 결정 구조 — 평면 그래프는 어디에나 있어요. 종이 위에 선이 서로 교차하지 않게 그릴 수 있는 그래프, 그게 바로 이 챕터의 주인공입니다. 단순해 보이는 이 조건이 오일러 공식, 4색 정리, 정다면체 분류 같은 놀라운 결과들로 이어진다는 게 신기하죠. 이번 챕터에서는 평면 그래프의 정의부터 시작해서, 간선 수의 한계를 구하고, \(K_5\)와 \(K_{3,3}\)이 왜 평면에 그릴 수 없는지 증명하고, 마지막엔 정다면체가 왜 정확히 5개뿐인지까지 살펴봅니다.
그래프를 종이에 그릴 때, 우리는 정점을 점으로 찍고 간선을 곡선으로 잇습니다. 그런데 간선들이 서로 가로지르지 않게 그릴 수 있을까요? 어떤 그래프는 손쉽게 가능하지만, 어떤 그래프는 아무리 돌려봐도 어딘가는 꼭 교차합니다. 이 차이를 수학적으로 다루는 게 바로 평면 그래프 이론이에요.
가장 유명한 도입 문제가 있습니다. 바로 세 집-세 우물 문제(three utilities puzzle)예요. 세 채의 집이 나란히 있고, 그 앞에 세 개의 우물(가스, 물, 전기라고 해도 좋아요)이 있습니다. 모든 집은 모든 우물에 연결되어야 하는데, 파이프들이 서로 교차하면 안 된다는 조건이 붙어요. 자, 종이 위에서 이걸 해낼 수 있을까요?
노트
한번 직접 그려보세요. 8개의 연결까진 어렵지 않게 됩니다. 그런데 마지막 9번째 연결에서 항상 막혀요. 우연이 아니라, 수학적으로 불가능하다는 게 곧 증명될 겁니다.
이 문제는 그래프 언어로 옮기면 \(K_{3,3}\), 즉 양쪽에 정점이 3개씩 있는 완전이분그래프를 평면에 교차 없이 그릴 수 있느냐는 질문이 됩니다. 결론부터 말하면, 답은 "안 된다"입니다. 그리고 왜 안 되는지를 증명하는 게 이 챕터의 핵심 도구가 돼요.
비슷하게 \(K_5\) — 정점 5개가 모두 서로 연결된 완전그래프 — 도 평면에 그릴 수 없습니다. 이 두 그래프, \(K_5\)와 \(K_{3,3}\)은 "평면 그래프가 아닌 가장 작은 두 가지" 같은 위치를 차지해요. 나중에 쿠라토프스키 정리에서 더 멋진 의미를 갖게 됩니다.
예제 13.1.1
\(K_4\)는 어떨까요? 정점 4개를 모두 연결한 완전그래프입니다. 일단 정사각형으로 그리면 두 대각선이 교차하지만, 한 정점을 가운데로 옮기고 나머지 셋을 삼각형으로 두르면 교차 없이 그릴 수 있어요. 따라서 \(K_4\)는 평면 그래프입니다.
이제 정의를 엄밀하게 적어봅시다. 직관은 충분히 쌓였으니까요.
정의 13.2.1 (평면 그래프)
그래프 \(G\)가 평면 그래프(planar graph)라는 것은, 평면 위에 \(G\)의 정점들을 점으로, 간선들을 두 끝 정점을 잇는 곡선으로 그릴 수 있되 서로 다른 두 간선이 끝점이 아닌 곳에서 절대 교차하지 않도록 그릴 수 있다는 뜻입니다.
주의할 점이 있어요. 평면 그래프인 것과 평면에 "교차 없이 그려진" 것은 약간 다릅니다. 같은 그래프를 어떤 식으로 그리느냐에 따라 교차가 생길 수도 있고 없을 수도 있어요. 평면 그래프란 "교차 없이 그릴 수 있는 방법이 적어도 하나 존재하는" 그래프를 말합니다.
평면 위에 교차 없이 그려진 그래프는 평면을 여러 영역으로 나눕니다. 이 각 영역을 면(face)이라고 불러요.
정의 13.2.2 (면)
평면에 교차 없이 그려진 그래프의 면은 그래프의 간선들로 둘러싸인 평면의 연결된 영역입니다. 그래프의 바깥쪽 무한히 펼쳐진 영역도 하나의 면으로 셉니다(이를 외부면이라고 부릅니다).
예제 13.2.3
삼각형(\(K_3\))을 평면에 그리면 면이 두 개 있습니다. 삼각형 안쪽 영역 하나, 그리고 삼각형 바깥의 무한 영역 하나. \(V=3,\ E=3,\ F=2\)예요.
정사각형 모양 \(C_4\)도 마찬가지로 \(V=4,\ E=4,\ F=2\). 안쪽과 바깥쪽.
그런데 \(K_4\)를 평면에 잘 그리면 (한 정점을 삼각형 안에 넣어서) 작은 삼각형 영역 3개 + 바깥 무한 영역 1개 = \(F=4\). \(V=4,\ E=6,\ F=4\)네요.
노트
외부면을 빼먹는 실수가 정말 흔합니다. "내가 둘러싼 영역만 면 아닌가?" 싶지만, 수학적으로는 그래프가 둘러싸지 못한 무한히 큰 바깥쪽도 똑같이 한 영역으로 취급해요. 면을 셀 때 항상 +1을 잊지 마세요.
위 예제들을 다시 봅시다. \(V-E+F\)를 계산해보세요.
전부 \(2\)예요. 우연이 아닙니다.
정리 13.3.1 (오일러 공식)
연결된 평면 그래프를 평면에 교차 없이 그렸을 때, 정점 수 \(V\), 간선 수 \(E\), 면 수 \(F\)는 항상 다음을 만족합니다. \[ V - E + F = 2. \]
증명 (간선 수에 대한 귀납)
간선 수 \(E\)에 대한 귀납으로 보입니다.
기저: \(E=0\)이면 연결그래프이므로 \(V=1\), 면은 외부면 하나뿐이라 \(F=1\). \(1-0+1=2\). 성립합니다.
귀납 단계: \(E\geq 1\)일 때, 두 가지 경우로 나눕니다.
(i) 그래프에 사이클이 있으면, 어떤 사이클 위의 간선 \(e\)를 골라 제거합시다. \(e\)는 두 면(사이클 안쪽과 바깥쪽)의 경계였으므로, 제거하면 두 면이 하나로 합쳐져 면 수가 1 줄어들어요. 정점 수는 그대로, 간선 수는 1 줄어들고 그래프는 여전히 연결입니다. 귀납 가정에 의해 \(V-(E-1)+(F-1)=2\), 즉 \(V-E+F=2\). 성립.
(ii) 그래프에 사이클이 없으면 그것은 트리입니다. 트리에서는 잎(degree 1 정점)을 하나 떼어냅시다. 정점과 간선이 각각 1씩 줄고, 면 수는 그대로 1입니다(트리는 사이클이 없으니 외부면만 존재). 귀납 가정에 의해 \((V-1)-(E-1)+F=2\), 즉 \(V-E+F=2\). 성립.
∎
오일러 공식은 단순해 보이지만 굉장히 강력합니다. \(V, E\) 둘 중 하나만 알아도 면 수에 제약이 생기고, 곧 보겠지만 평면 그래프의 간선 수에 상한을 강제하기까지 합니다.
평면 그래프는 정점 수에 비해 너무 많은 간선을 가질 수 없습니다. 직관적으로, 정점이 \(V\)개라도 간선이 너무 많으면 어느 순간 교차하지 않고는 그릴 수가 없거든요. 이걸 수식으로 깔끔하게 잡아봅시다.
핵심 아이디어는 면-간선 이중 계산(double counting)입니다. 각 면의 경계 길이(둘러싼 간선 수)를 모두 합하면 어떻게 될까요? 모든 간선은 양쪽에 면이 하나씩 붙어 있으니까(같은 면이 양쪽일 수도 있지만 그래도 두 번 카운트됨), 이 합은 정확히 \(2E\)와 같습니다.
정리 13.4.1 (간선 수 상한)
\(V\geq 3\)인 단순 연결 평면 그래프에서 \[ E \leq 3V - 6. \] 또한 그래프가 이분(bipartite)이면 더 강하게 \[ E \leq 2V - 4. \]
증명
단순 그래프이고 \(V\geq 3\)이라면 어떤 면도 길이 1이나 2의 경계를 가질 수 없어요(루프나 다중 간선이 없으니까). 따라서 모든 면의 경계 길이는 최소 \(3\)입니다. 면이 \(F\)개일 때 경계 길이의 총합은 적어도 \(3F\)이고, 이중 계산에서 이 합은 \(2E\)이므로 \[ 3F \leq 2E \quad\Rightarrow\quad F \leq \frac{2E}{3}. \] 오일러 공식 \(V-E+F=2\)에서 \(F=2-V+E\)이므로 \[ 2 - V + E \leq \frac{2E}{3} \quad\Rightarrow\quad E \leq 3V-6. \]
이분 그래프의 경우, 짝수 길이 사이클만 가지므로 모든 면의 경계 길이는 최소 \(4\)입니다. 같은 논리로 \(4F\leq 2E\), 즉 \(F\leq E/2\). 오일러 공식과 결합하면 \[ 2-V+E \leq \frac{E}{2} \quad\Rightarrow\quad E \leq 2V-4. \]
∎
예제 13.4.2
정점이 10개인 평면 그래프는 간선이 최대 몇 개? \(3\cdot 10-6=24\)개. 그런데 이 그래프가 이분이라면? 최대 \(2\cdot 10-4=16\)개로 더 줄어요.
노트
이 부등식의 진짜 위력은 "평면이 아님"을 증명할 때 나옵니다. 어떤 그래프가 \(E>3V-6\)이면, 그건 평면 그래프가 될 수 없어요. 대우(contrapositive)로 쓰는 게 핵심이에요.
13.1에서 미뤄둔 약속을 갚을 시간이에요. \(K_5\)와 \(K_{3,3}\) 둘 다 평면 그래프가 아니라는 사실을 13.4의 부등식으로 정확히 증명할 수 있습니다.
정리 13.5.1
\(K_5\)는 평면 그래프가 아닙니다.
증명
\(K_5\)는 정점이 \(V=5\)개이고 모든 쌍이 간선으로 연결되어 있으니 간선이 \(E=\binom{5}{2}=10\)개입니다. 만약 \(K_5\)가 평면 그래프라면, \(V\geq 3\)이므로 \(E\leq 3V-6\)이 성립해야 하는데 \[ 3V-6 = 3\cdot 5 - 6 = 9. \] 그러나 \(E=10 > 9\)이므로 모순. 따라서 \(K_5\)는 평면 그래프가 아닙니다.
∎
정리 13.5.2
\(K_{3,3}\)은 평면 그래프가 아닙니다.
증명
\(K_{3,3}\)은 양쪽에 정점이 3개씩 있는 완전이분그래프이므로 \(V=6\), \(E=3\cdot 3=9\)입니다. 또한 이분 그래프죠. 만약 평면이라면 이분 평면에 대한 부등식 \(E\leq 2V-4\)이 성립해야 하는데 \[ 2V-4 = 2\cdot 6 - 4 = 8. \] 그런데 \(E=9 > 8\). 모순입니다. 따라서 \(K_{3,3}\)은 평면 그래프가 아니에요.
∎
노트
\(K_{3,3}\)에 일반 부등식 \(E\leq 3V-6=12\)를 그대로 쓰면 \(9\leq 12\)라 모순이 안 나옵니다. 그래서 이분이라는 추가 정보를 써서 \(2V-4\)라는 더 빡빡한 부등식을 적용해야 모순을 만들 수 있어요. 이게 "이분 그래프엔 더 좋은 한계가 있다"의 진짜 이유입니다.
드디어 세 집-세 우물 퍼즐의 답이 나왔어요. 절대로 못 그립니다. 종이에서 못 그릴 뿐 아니라, 평면이라는 공간 자체에서 불가능합니다(도넛 표면 같은 데서는 가능하답니다, 흥미롭게도).
지도를 색칠할 때, 인접한 나라(국경을 맞댄 나라)에 같은 색을 쓰지 않으려면 색이 몇 개 필요할까요? 각 나라를 정점으로, 인접한 나라끼리 간선으로 잇는 그래프를 만들면, 이 그래프는 자연스럽게 평면 그래프가 됩니다. 따라서 지도 색칠 문제는 곧 평면 그래프의 채색수(chromatic number) 문제예요.
정리 13.6.1 (5색 정리)
모든 평면 그래프는 5색으로 채색 가능합니다. 즉 평면 그래프의 채색수는 \(\chi(G)\leq 5\).
증명 스케치
먼저 보조 사실: 모든 평면 그래프에는 차수가 \(5\) 이하인 정점이 적어도 하나 있습니다. 왜냐하면 만약 모든 정점이 차수 \(\geq 6\)이라면 \(2E=\sum_v \deg(v)\geq 6V\), 즉 \(E\geq 3V\)인데 평면 그래프에선 \(E\leq 3V-6 < 3V\)이라 모순이거든요.
이제 정점 수 \(V\)에 대한 강귀납을 사용합니다. \(V\leq 5\)이면 자명. \(V>5\)일 때, 차수 \(\leq 5\)인 정점 \(v\)를 잡고, \(v\)를 일단 떼어내요. 남은 그래프는 정점 수가 적으니 귀납 가정에 의해 5색 채색이 가능합니다.
이제 \(v\)에 색을 줘야 합니다. \(v\)의 이웃은 최대 5개. 만약 그들이 5색 중 하나라도 안 쓴 색이 있다면 그 색을 \(v\)에 칠하면 끝. 만약 5명이 5색을 모두 정확히 다르게 쓰고 있다면? 이 경우엔 켐페 사슬(Kempe chain) 논증을 써서 두 이웃의 색을 교묘하게 바꿔치기해 한 색을 비워낼 수 있습니다(자세한 건 좀 더 정교한 케이스 분석이 필요해요).
∎
정리 13.6.2 (4색 정리, Appel-Haken 1976)
모든 평면 그래프는 4색으로 채색 가능합니다.
노트
4색 정리는 100년 넘게 미해결 난제였다가 1976년에 Appel과 Haken이 컴퓨터의 도움으로 증명했어요. 약 1500개의 환원 가능한 구성을 컴퓨터로 일일이 검증한 증명이라, 처음엔 "이걸 진짜 증명이라 부를 수 있나?" 논쟁이 있었답니다. 지금은 받아들여진 정리지만, 이 챕터에선 손으로 증명할 수 있는 5색 정리까지만 다룹니다.
오일러 공식의 가장 우아한 응용 중 하나는 정다면체(Platonic solid)가 정확히 5개뿐이라는 사실의 증명입니다. 정다면체란 모든 면이 합동인 정다각형이고 모든 꼭짓점이 동일한 모양으로 만나는 볼록다면체예요.
왜 평면 그래프가 다면체랑 관련이 있을까요? 볼록다면체를 잡고 그 한 면을 풍선 늘이듯이 평면 위로 펼치면, 다면체의 정점-간선 구조가 평면 그래프가 됩니다. 그러면 오일러 공식 \(V-E+F=2\)를 그대로 적용할 수 있어요(여기서 \(F\)는 다면체의 면 수와 일치하고, 외부면이 곧 펼친 그 면에 해당합니다).
각 면이 \(p\)각형이고 각 꼭짓점에 \(q\)개의 면이 모인다고 합시다. 그러면:
오일러 공식에 대입하면 \[ \frac{2E}{q} - E + \frac{2E}{p} = 2 \quad\Rightarrow\quad \frac{1}{p}+\frac{1}{q} = \frac{1}{2}+\frac{1}{E}. \] \(E>0\)이므로 우변 \(>1/2\), 즉 \[ \frac{1}{p}+\frac{1}{q} > \frac{1}{2}. \] 또한 \(p\geq 3\)(다각형이니), \(q\geq 3\)(꼭짓점에 최소 3면 모임).
이 부등식 \(\frac{1}{p}+\frac{1}{q}>\frac{1}{2}\)에 \(p,q\geq 3\)인 정수해를 모두 찾아봅시다.
따라서 가능한 \((p,q)\)는 정확히 5쌍: \((3,3),(3,4),(3,5),(4,3),(5,3)\). 이 다섯이 정사면체부터 정이십면체까지 다섯 정다면체에 대응합니다.
| 이름 | \(p\) | \(q\) | \(V\) | \(E\) | \(F\) |
|---|---|---|---|---|---|
| 정사면체 (Tetrahedron) | 3 | 3 | 4 | 6 | 4 |
| 정육면체 (Cube) | 4 | 3 | 8 | 12 | 6 |
| 정팔면체 (Octahedron) | 3 | 4 | 6 | 12 | 8 |
| 정십이면체 (Dodecahedron) | 5 | 3 | 20 | 30 | 12 |
| 정이십면체 (Icosahedron) | 3 | 5 | 12 | 30 | 20 |
각 행의 \(V-E+F\)를 계산해보면 모두 \(2\)예요. 오일러 공식이 다면체의 세계에서도 그대로 살아있다는 게 정말 멋지죠.
노트
플라톤은 이 다섯 다면체를 4원소(불, 흙, 공기, 물)와 우주 자체에 대응시켰어요. 수학적으로는 그저 부등식 \(1/p+1/q>1/2\)의 정수해가 다섯이라는 단순한 사실인데, 이 단순함이 도리어 우주의 어떤 미감을 자아내는 것 같습니다.
지금까지 본 부등식 \(E\leq 3V-6\)은 평면 그래프가 되기 위한 필요조건이지만 충분조건은 아닙니다. 즉, 부등식을 만족하는데도 평면이 아닌 그래프가 있을 수 있어요. 그러면 평면 그래프를 그래프 자체의 구조만으로 완전히 특징지을 방법이 있을까요?
놀랍게도 답은 "예"입니다. 그것도 \(K_5\)와 \(K_{3,3}\)을 다시 만나면서요.
정리 13.8.1 (쿠라토프스키 정리, 1930)
그래프 \(G\)가 평면 그래프인 것은 \(G\)가 \(K_5\) 또는 \(K_{3,3}\)의 분할(subdivision)을 부분그래프로 포함하지 않을 필요충분조건입니다.
여기서 분할이란 어떤 간선의 중간에 새로운 차수-2 정점을 끼워넣는 연산을 반복해서 얻는 그래프를 말합니다. 직관적으로는 간선을 "여러 토막으로 잘라낸" 그래프예요. 본질적으로는 같은 그래프인 셈이죠.
이 정리의 의미는 깊습니다. 평면이 아닌 모든 그래프는 그 안에 어떤 식으로든 \(K_5\)나 \(K_{3,3}\)을 "숨기고" 있다는 말이거든요. 이 둘이 비평면성의 근원적인 두 가지 패턴이라는 거예요.
노트
비슷한 정리로 와그너 정리(Wagner's theorem)가 있어요. 이 정리는 "분할" 대신 "마이너(minor)"라는 더 일반적인 연산을 써서 같은 결과를 말합니다: \(G\)가 평면이려면 \(K_5\)와 \(K_{3,3}\)을 마이너로 가지지 않아야 한다는 거죠. 이게 더 나아가면 그래프 마이너 이론(로버트슨-시모어 이론)이라는 거대한 분야로 이어집니다.
평면 그래프의 인식 자체는 효율적으로 풀 수 있는 문제이기도 합니다. 1974년 호프크로프트와 타잔이 \(O(V)\) 시간에 평면성을 판정하는 알고리즘을 제시했어요. 그래프 이론과 알고리즘이 만나는 멋진 지점이죠.
이 챕터를 마치면서, 평면 그래프가 단지 "예쁜 그림"의 문제가 아니라는 걸 다시 강조하고 싶어요. 회로 기판 설계에서는 평면성이 곧 단일 층에 인쇄 가능한지를 결정하고, 컴퓨터 그래픽에서는 평면 메시 분해가 텍스처 매핑의 기반이 됩니다. 단순한 정의에서 출발한 이론이 이렇게 풍부한 응용으로 뻗어나간다는 점이, 이산수학을 공부하는 즐거움 중 하나예요.