평면그래프

평면그래프(planar graph)는 평면 매장(plane embedding, plane graph)이 존재하는 그래프를 말한다. 평면 매장은 평면 [math]\displaystyle{ \mathbb R^2 }[/math]에 변끼리 겹치지 않게 그려진 그래프이며, 평면그래프는 평면 매장과 동형(isomorphic)인 그래프를 말한다. 평면에 그려졌으므로 그래프의 면을 가장 바깥에 있는 면인 무계 면/무한 면/외면(unbounded/infinite/external, outer face)과 외면이 아닌 유계 면/유한 면/내면(bounded/finite/inner face)으로 나눌 수 있다. 또한 평면과 곡면 종수(genus)가 같은 모든 곡면에 매장가능함은 평면그래프임과 동치이다.

쿠라토프스키 정리와 바그너 정리

평면그래프의 필요충분조건을 가장 간단하게 설명하는 정리이다. 쿠라토프스키 정리에 따르면, 그래프 [math]\displaystyle{ G }[/math]가 평면그래프일 필요충분조건은 [math]\displaystyle{ G }[/math]가 [math]\displaystyle{ K_5 }[/math]나 [math]\displaystyle{ K_{3,3} }[/math]의 세분할(subdivision)과 동형(isomorphic)인 부분그래프를 갖지 않는 것이다. 즉 [math]\displaystyle{ K_5 }[/math]나 [math]\displaystyle{ K_{3,3} }[/math]을 위상적 마이너로서 갖지 않는 것이다. 이와 비슷하게, 바그너 정리는 그래프 [math]\displaystyle{ G }[/math]가 평면그래프일 필요충분조건은 [math]\displaystyle{ G }[/math]가 [math]\displaystyle{ K_5 }[/math]나 [math]\displaystyle{ K_{3,3} }[/math]를 마이너로서 갖지 않는 것이다.

오일러 다면체 정리

오일러 다면체 정리(Euler's polyhedral theorem)는 연결된 평면그래프 [math]\displaystyle{ G }[/math]의 오일러 표수 [math]\displaystyle{ \chi_E(G) = v-e+f }[/math]가 항상 2임을 말한다. 예를 들어, 삼각형 [math]\displaystyle{ K_3 }[/math]의 경우엔 [math]\displaystyle{ v=3,~e=3,~f=2 }[/math] (내면과 외면)이므로 [math]\displaystyle{ v-e+f =2 }[/math]가 성립한다. 하지만 연결되지 않은 평면그래프에서는 당연하게도 성립하지 않는다. 다만 이때는 [math]\displaystyle{ v - e + f \ge 2 }[/math]가 성립하게 된다. (연결되도록 변을 더 그려넣으면, [math]\displaystyle{ e }[/math]가 증가하여 [math]\displaystyle{ \chi_E(G) = 2 }[/math]가 될 것이다. 따라서 [math]\displaystyle{ e }[/math]가 더 작다면 오일러 표수는 2 이상이 될 것이다.)

오일러 표수를 이용하면 변의 수와 꼭짓점의 수 사이의 부등식을 찾을 수 있다. 먼저, 그래프의 안둘레(girth) [math]\displaystyle{ g }[/math]를 최소 순환 길이라고 정의하자. (없으면 무한대.) 예를 들어 고리가 있는 그래프는 안둘레가 1이고, 단순그래프는 안둘레가 3 이상이다. 만약 순환이 없다면, 즉 안둘레가 무한대이면, 그 그래프는 나무이고 즉 [math]\displaystyle{ v=e+1,~f=1 }[/math]임을 알기에 별 다른 부등식이 필요하지 않다. 이제 안둘레가 [math]\displaystyle{ 3\le g \lt \infty }[/math]라고 가정하자. 그러면 (한 면, 그 면과 인접한 변)의 순서쌍의 개수는 최대 [math]\displaystyle{ 2e }[/math] 개이며(한 변은 최대 두 개의 면과 만난다), 최소 [math]\displaystyle{ gf }[/math] 개이다(한 면에는 [math]\displaystyle{ g }[/math] 개 이상의 인접한 변이 있다). 따라서 [math]\displaystyle{ 2e \ge gf }[/math]이며, 오일러 다면체 정리에 의하여

[math]\displaystyle{ \displaystyle 2=v-e+f \le v-e+\frac 2 g e = v - \frac{g-2}{g} e \implies e \le \frac g {g-2} (v-2) }[/math]

이 됨을 알 수 있다. 예를 들어 단순 평면그래프는 [math]\displaystyle{ e\le 3v-6 }[/math]을 만족하며, 삼각형이 없는 단순그래프나 이분그래프 같은 경우에는 안둘레가 4 이상이므로 [math]\displaystyle{ e\le 2v - 4 }[/math]이다.

이를 이용하면 평균 차수가

[math]\displaystyle{ \displaystyle \operatorname{deg}(G) = \frac 1 v \sum_{x \in V(G)} \operatorname{deg}_G(x) = \frac{2e}{v} \le \frac{2g}{g-2} \frac{v-2}v \lt \frac{2g}{g-2} }[/math]

이므로, 차수가 [math]\displaystyle{ \frac{2g}{g-2} }[/math]보다 작은 꼭짓점이 반드시 존재하게 된다. 이는 그래프 채색 관련 문제를 다룰 때 유용하게 사용된다.