오일러의 다면체 정리 증명

오일러의 다면체 정리 증명

정리 1

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


설명

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


  1. Wilson. (1970). Introduction to Graph Theory: p66. ↩︎

댓글