그래프이론에서 신기한 결과중에 하나인 Euler formula (오일러 공식)에 대해 알아보겠습니다. planar graph가 가지고 있는 특성을 Euler Formula 를 통해 알 수 있습니다. 명제와 증명 자체는 간단하니까 한번 쭉 봐주시면 되겠습니다. 그러면 이제 Euler formula (오일러 공식)에 대해 본격적으로 알아보겠습니다.
Euler formula (오일러 공식)
Euler formula는 simple connected planar graph에 관한 글이다. 아래의 참고글을 읽어오면 도움이 될것이다.
[그래프이론 (Graph Theory)] Planar Graphs, drawing, crossing, embedding, plane graph, faces, dual graph
위의 글을 읽었다면 Euler formula 에 대해 알아보자.
Euler formula(오일러 공식): G 를 connected이고 simple 인 planar graph 라고 합시다. n = n(G), e = e(G) 이고 f 를 face의 총갯수라고 합시다. 그러면 아래의 식이 성립합니다.
n-e+f=2
명제는 간단합니다. connected simple planar graph 의 종류는 정말 무수히 많을 텐데 공통적으로 갖고 있는 성질이 n-e+f=2라니 놀라울 뿐이네요.
Euler formula (오일러 공식) 증명
증명도 간단합니다. 귀납법을 사용할 것이에요. 귀납법을 사용하기 위해 명제를 정의해보겠습니다.
p(n): vertex 갯수가 n 개인 connected simple planar graph 에 대하여 n-e+f=2 는 성립한다. 여기서 n = n(G) , e=e(G) 이고 f 는 G의 face의 총갯수입니다.
n=1 일 때, G 의 vertex의 갯수는 한개이고 edge는 한개이상이어야 합니다. 그리고 이 edge는 loop 여야만 하지요. 잘 생각해보면 f=e+1 임을 알 수 있습니다. 따라서 n-e+f = 1-e+e+1=2 이 성립합니다.
이제 귀납법을 사용하기 위하여 n=k 일 때 성립한다고 가정합니다. k 는 1 보다 크거나 같은 자연수입니다.
이제 G 를 |V(G)|=k+1 이 simple connected planar graph 라고 합시다. 그러면 서로 다른 vertex x,y가 존재하여 이 두 vertex를 잇는 edge e* 가 존재합니다. e* 를 contraction 한 그래프 G\cdot e* 에 대해 생각해봅시다. G\cdot e* 에 대하여 n(G\cdot e*) = n(G) -1 , e(G\cdot e*) =e(G)-1 입니다. face의 숫자는 G\cdot e* 나 G 모두 동일합니다. n(G\cdot e * ) = k-1 이므로 아래의 formula가 성립합니다.
n(G\cdot e*)-e(G\cdot e*) + f = 2그런데 이것을 다시 써보면 n(G\cdot e*) - e(G\cdot e*) +f = n(G)-1 - (e(G)-1)+f = n(G)-e(G)+f = 2 입니다. 따라서 수학적 귀납법에 의해 모든 simply connected planar graph 에 대하여 euler formula 가 성립한다는 것을 알 수 있습니다.