📂그래프이론

오일러의 다면체 정리 증명

개요

오일러의 다면체 정리는 오일러의 표수 , 그래프 이론에서는 그냥 오일러 공식 으로도 불린다. 기하학적으로는 공간도형의 점, 선, 면이 #점-#선+#면=2 의 관계를 따른다는 의미를 갖는다. 예로써 정육면체를 생각해보면, $8$ 개의 점과 $12$ 개의 선, $6$ 개의 면을 가지고 있어 $8-12+6=2$ 가 성립한다.

정리 ¹

연결 평면 그래프 $G$ 에 대해, $n:=|V(G)|$, $m:=|E(G)|$, $f$ 를 페이스의 수라고 하면 $$ n-m+f=2 $$

---

• 평면 그래프가 그려지면서 평면 상에서 구분되는 영역들을 페이스라 부른다.

증명

전략: 여러가지가 있으나 이 포스트에서는 기초적인 그래프 이론을 사용한 증명을 소개하려 한다. 경우를 나눠서 수학적 귀납법을 적용하면 어렵지 않게 보일 수 있다.

---

Case 1. $n=1$

$G$ 가 연결이므로 $m=1$, 무한 페이스 외엔 페이스가 없으므로 $f=1$ 이 된다. 따라서 $1-0+1=2$ 가 성립한다.

---

Case 2. $n>1$ 이고 $G$ 가 트리 그래프인 경우

$G$ 가 트리이므로 $m=n-1$ 이고, 사이클을 포함하고 있지 않으므로 $f=1$ 이다. 따라서 $n-(n-1)+1=2$ 가 성립한다.

---

Case 3. $n>1$ 이고 $G$ 가 트리 그래프가 아닌 경우

$G$ 는 사이클을 적어도 하나 포함하고 있는데, 이 사이클에 놓인 에지 하나를 $e$ 라고 해보자. 그 $e$ 를 제거한 새로운 그래프 $G-e$ 에 대해 $$ |V(G-e)|=n \\ |E(G-e)|=m-1 $$ 한편 사이클을 감싸고 있던 $e$ 가 제거됨으로써 $e$ 를 경계로 하던 두 페이스가 하나로 합쳐진다. 따라서 $G-e$ 의 페이스의 수는 $f-1$ 이 되고, $n-(m-1)+(f-1)=n-m-f=2$ 이 성립한다.

■

한편 오일러의 다면체 정리는 $k$ 개의 컴포넌트에 대해 다음과 같이 일반화될 수 있다. 위의 정리는 특히 연결 그래프, 즉 $k=1$ 인 경우에 대한 특수한 경우가 된다.

일반화

평면 그래프 $G$ 에 대해, $n:=|V(G)|$, $m:=|E(G)|$, $f$ 를 페이스의 수, $k$ 를 컴포넌트의 수라고 하면 다음이 성립한다. $$ n-m+f=k+1 $$ 이는 그래프의 연결성에 대한 오일러 다면체 정리의 일반화다.

같이보기

그래프이론에서의 오일러 표수

원래 오일러 표수는 그래프 이론에서 가장 유명한데, 오일러의 다면체 정리 혹은 오일러 공식은 연결 평면 그래프에 대해서 $\chi = 2$ 이라는 그래프이론의 정리다.

기하학에서의 오일러 지표

가우스-보네 정리의 방정식을 만족시키는 정수로써 정의된다.

대수위상에서의 오일러 지표

각 차원의 베티 수의 교대합으로써 정의된다.