[그래프이론(graph theory)]simple planar graph 의 edge의 총 갯수

이번 글에서는 simple planar graph 의 edge의 총 갯수를 가늠해 보겠습니다. 명제와 증명 자체는 간단한데 이것을 알면 planar graph 를 구분해내는데 도움이 될것입니다. 그러면 이제 simple planar graph 의 edge 수에 대해 알아보도록 하겠습니다.





simple planar graph 의 edge 갯수에 관한 부등식

G 를 simple planar graph 라고 합시다. 그리고 G 의 vertex가 적어도 세개있다고 합시다.
그러면

  1. e(G) \leq 3n(G) - 6 성립합니다.
  2. G 가 traingle 을 가지고 있지 않다면 e(G) \leq 2 n(G) -4 입니다.

(증명) 우선 G 가 connected 일 때만 증명하면 된다는 것에 주목해봅시다. 왜그런지는 생각을 해보시고요. 이제 connecte graph G 에 대해 증명하겠습니다.

1. euler formula 에 의하여 n - e + f = 2 이 성립합니다. 여기서 n = n(G), e = e(G) 이고 f 는 face의 총 갯수입니다. n \geq 3 이므로 e+2 = n+f \geq 3 +f 이므로 e \geq f 는 항상 성립합니다. f_1,f_2,...,f_k G 가 갖고 있는 face이고 l(f_i ) 를 face f_i 의 길이라고 합시다. 그러면! 아래의 공식이 성립한다는 것은 이미 알고 있죠

2e = \sum_i l(f_i)

그런데 G 가 simple graph 이고 n(G) \geq 3 이므로 무조건 l(f_i) \geq 3 이어야 합니다. 따라서!

2e = \sum_i l(f_i) \geq 3 f =3 ( e-n+2) 이고 e \geq 3n -6 이 성립합니다.

2. 1의 경우와 비슷합니다. 여기서 다른 점은 G 는 triangle 을 갖고 있지 않기 때문에 l(f_i) \geq 4 라는 점입니다. 이 사실을 이용하면 아래와 같이 증명할 수 잇습니다.

2e = \sum_i l(f_i) \geq 3 f =4 ( e-n+2) 이고 e \geq 2n -4 이 성립합니다.

Leave a Comment