평면그래프
오일러 공식 V−E+F=2, K₅와 K₃,₃
개요 — 동기·문제의식
그래프를 종이에 그릴 때 간선들이 꼭 교차해야 하는가? 이 질문이 평면그래프(planar graph) 의 출발점이다. 어떤 그래프는 아무리 다시 그려도 교차가 피할 수 없고, 어떤 그래프는 교차 없이 평면에 배치할 수 있다.
평면그래프의 첫 핵심 정리는 Euler 공식이다. 연결된 plane graph에서 정점 수 $V$, 간선 수 $E$, face 수 $F$ 는 항상 $$V-E+F=2$$ 를 만족한다.1
이 단순한 식 하나가 $K_5$ 와 $K_{3,3}$ 의 비평면성을 즉시 설명하고, 지도 색칠 문제와 그래프 채색으로 이어진다.
직관
평면에 교차 없이 그린 연결 그래프는 평면을 여러 영역(face)으로 나눈다. 간선을 하나 추가해 순환을 만들면 기존 face 하나가 둘로 갈라진다. 그래서 간선 수가 1 늘고 face 수도 1 늘어 $V-E+F$ 는 변하지 않는다.
트리에서 시작하면 face는 바깥 영역 하나뿐이다. $n$개 정점의 트리는 간선이 $n-1$개이므로 $V-E+F=n-(n-1)+1=2$다. 순환을 만드는 간선을 추가할 때마다 $E$ 와 $F$ 가 같이 늘어나므로 값은 계속 2다.
따라서 Euler 공식은 위상수학의 냄새가 나는 조합 공식이다. 실제로 다른 곡면에서는 오른쪽 값이 2가 아니라 곡면의 Euler characteristic가 된다.
정의
drawing: 정점을 평면의 점으로, 간선을 양 끝점을 잇는 단순 곡선으로 그린 것.
plane graph: 이미 평면에 교차 없이 그려진 그래프.
planar graph: 어떤 plane drawing을 갖는 추상 그래프.
face: plane graph를 평면에 그렸을 때 평면에서 그래프를 뺀 연결 영역. 무한한 바깥 영역도 face다.
| 용어 | 의미 |
|---|---|
| embedding | 추상 그래프를 plane graph로 실현한 것 |
| outer face | 무한한 바깥 face |
| face boundary | face를 둘러싸는 closed walk 또는 cycle |
| triangulation | 모든 face가 삼각형으로 둘러싸인 maximal plane graph |
| subdivision | 간선을 path로 대체하여 얻는 그래프 |
| topological minor | 어떤 subdivision을 부분그래프로 포함하는 관계 |
| minor | edge deletion, vertex deletion, contraction으로 얻는 관계 |
평면성은 추상 그래프의 성질이고, face는 특정 embedding에 의존한다. 그러나 연결 plane graph의 $V-E+F$ 값은 embedding과 무관하게 2다.
주요 정리
정리 1 (Euler 공식). 연결 plane graph $G$ 가 $n$개 정점, $m$개 간선, $f$개 face를 가지면 $$n-m+f=2.$$
증명 보기
증명. $G$ 가 tree이면 $m=n-1$, $f=1$ 이므로 성립한다. 이제 $G$ 에 cycle이 있으면 cycle 위 간선 $e$ 하나를 지운다. $e$ 는 bridge가 아니므로 연결성은 유지된다. plane drawing에서는 $e$ 양쪽의 두 face가 하나로 합쳐지므로 $m$ 과 $f$ 가 각각 1씩 줄고 $n-m+f$ 는 변하지 않는다. 이 과정을 반복하면 spanning tree에 도달하고, 그 값이 2였으므로 원래 그래프도 2다. ∎
정리 2 (간선 수 상계). $n\ge3$ 인 단순 planar graph는 $$m\le 3n-6$$ 를 만족한다.2
증명 보기
증명. 연결이라고 가정해도 충분하다. 모든 face boundary 길이는 적어도 3이고, 각 간선은 face boundary 길이 합에 두 번 세어진다. 따라서 $3f\le2m$. Euler 공식 $n-m+f=2$ 에서 $f=2-n+m$ 을 대입하면 $3(2-n+m)\le2m$, 즉 $m\le3n-6$. ∎
정리 3 (triangle-free planar bound). $n\ge3$ 인 triangle-free 단순 planar graph는 $$m\le 2n-4$$ 를 만족한다.
증명 보기
증명. 모든 face boundary 길이가 적어도 4이므로 $4f\le2m$ 이다. Euler 공식에 대입하면 $4(2-n+m)\le2m$, 즉 $m\le2n-4$. ∎
정리 4 ($K_5$ 와 $K_{3,3}$ 의 비평면성). $K_5$ 와 $K_{3,3}$ 는 planar가 아니다.
증명 보기
증명. $K_5$ 는 $n=5$, $m=10$ 인데 planar라면 $m\le3n-6=9$ 이어야 하므로 모순. $K_{3,3}$ 는 triangle-free이고 $n=6$, $m=9$ 인데 planar라면 $m\le2n-4=8$ 이어야 하므로 모순. ∎
정리 5 (Kuratowski 정리, 안내). 유한 그래프가 planar일 필요충분조건은 $K_5$ 또는 $K_{3,3}$ 의 subdivision을 부분그래프로 포함하지 않는 것이다.3
의미. Euler 부등식은 $K_5$, $K_{3,3}$ 가 planar가 아님을 보이지만, Kuratowski 정리는 이 둘이 모든 비평면성의 근본 장애물이라고 말한다.
예제
예제 1 (tree). 어떤 tree도 planar다. 연결 plane tree는 face가 하나뿐이고 $n-(n-1)+1=2$ 를 만족한다.
예제 2 ($C_n$). 순환 $C_n$ 은 평면을 안쪽 face와 바깥 face 두 개로 나눈다. $V=n$, $E=n$, $F=2$ 이므로 Euler 공식이 맞다.
예제 3 ($K_4$). $K_4$ 는 planar다. 삼각형 하나를 바깥 face로 두고 네 번째 정점을 내부에 놓아 세 꼭짓점에 연결하면 된다. $V=4$, $E=6$, $F=4$.
예제 4 ($K_5$). 간선 수가 너무 많다. $10>3\cdot5-6=9$ 이므로 planar가 아니다.
예제 5 ($K_{3,3}$). 이분그래프라 triangle이 없다. triangle-free planar bound를 쓰면 $9>2\cdot6-4=8$ 이므로 planar가 아니다.
예제 6 (정육면체 그래프). 정점 8개, 간선 12개, face 6개를 가진 planar graph다. $8-12+6=2$.
예제 7 (Petersen 그래프). Petersen 그래프는 $K_{3,3}$ subdivision을 포함하는 방식으로 비평면성을 볼 수 있다. 단순히 $m\le3n-6$ 만으로는 $15\le24$ 라서 비평면성이 드러나지 않는다.
예제 8 (지도와 dual graph). 지도에서 지역을 정점으로 두고 국경을 공유하면 그래프가 된다. 반대로 plane graph의 face를 정점으로 두고 인접 face를 잇는 dual graph도 만들 수 있다.
흔한 오해와 함정
- plane과 planar를 혼동하기 — plane graph는 특정 embedding이 주어진 그래프이고, planar graph는 그런 embedding이 존재한다는 추상 성질이다.
- 간선 교차점도 정점으로 세기 — drawing에서 우연히 교차한 점은 그래프의 정점이 아니다. 평면 embedding에서는 그런 교차가 없어야 한다.
- Euler 공식에서 바깥 face를 빼먹기 — 외부 영역도 반드시 face로 세어야 한다.
- $m\le3n-6$ 이 충분조건이라고 생각하기 — 이 부등식은 필요조건일 뿐이다. Petersen 그래프처럼 부등식을 만족해도 nonplanar일 수 있다.
- 비연결 그래프에 $V-E+F=2$ 를 그대로 적용하기 — 연결성분이 $c$개이면 plane graph에서 $V-E+F=1+c$ 형태로 바뀐다.
- $K_5$, $K_{3,3}$ 자체만 금지하면 된다고 생각하기 — subdivision 또는 minor 형태가 중요하다.
큰 그림 / 연결
Euler 공식은 graphs basics and trees의 tree 공식 $E=V-1$ 에서 출발해 face라는 위상 정보를 추가한 것이다. 그래서 평면그래프는 graph theory와 topology의 가장 빠른 접점이다.
그래프 채색에서 평면성은 색칠 정리의 핵심 가정이 된다. Euler 부등식은 모든 planar graph가 차수 5 이하의 정점을 가진다는 사실을 주고, 이것이 5색 정리의 귀납 출발점이다.
Kuratowski 정리는 graph minors frontier의 시작점이다. 금지된 작은 구조가 전체 graph class를 특징짓는다는 생각은 Robertson-Seymour graph minor theorem으로 크게 확장된다.
평면 duality는 network flows와도 연결된다. plane graph에서 cycle과 cut은 dual graph에서 서로 바뀌며, flow-coloring duality의 배경이 된다.
연습문제
- 연결 plane tree에서 Euler 공식을 직접 확인하라.
- $C_6$ 의 face 수를 구하고 Euler 공식을 확인하라.
- $K_4$ 의 plane drawing에서 face 수를 구하라.
- $n\ge3$ 단순 planar graph에서 평균 차수가 6보다 작음을 증명하라.
- 모든 planar graph가 차수 5 이하의 정점을 가진다는 것을 보여라.
- $K_5$ 의 비평면성을 $m\le3n-6$ 으로 증명하라.
- $K_{3,3}$ 의 비평면성을 triangle-free bound로 증명하라.
- 비연결 plane graph에서 $V-E+F=1+c$ 를 유도하라.
- Petersen 그래프에 대해 간선 수 부등식만으로는 비평면성을 보일 수 없음을 확인하라.
힌트 / 정답
- $E=V-1$, $F=1$ 이므로 $V-E+F=V-(V-1)+1=2$.
- $V=6$, $E=6$ 이므로 $F=2$.
- $V=4$, $E=6$ 이므로 $F=4$.
- $2m\le6n-12$ 이므로 평균 차수 $2m/n\le6-12/n<6$.
- 평균 차수가 6보다 작으므로 모든 정점 차수가 6 이상일 수 없다.
- $K_5$ 는 $n=5$, $m=10$ 이고 planar라면 $m\le9$ 여야 한다.
- $K_{3,3}$ 는 triangle-free, $n=6$, $m=9$ 이고 planar라면 $m\le8$ 여야 한다.
- 각 연결성분을 하나씩 추가할 때 새 바깥 영역 배치 때문에 값이 1씩 증가한다. 또는 성분별 Euler 공식을 합치고 공통 outer face가 하나로 합쳐짐을 세어라.
- Petersen 그래프는 $n=10$, $m=15$, $3n-6=24$ 이므로 부등식 위반이 없다.
관련 개념
- graphs basics and trees — tree와 Euler 공식의 출발점
- 그래프 채색 — 5색 정리와 4색 정리
- connectivity and menger — 2-connected plane graph와 face 경계
- graph minors frontier — Kuratowski에서 graph minor theorem으로
- network flows — planar duality와 flow-coloring duality
- reading path diestel — Diestel 4장 학습 경로