📂그래프이론

심플 평면 그래프의 성질

정리 ¹

$G$ 가 심플 평면 그래프라고 하자.

• [1]: $G$ 가 연결 그래프고 $n \ge 3$ 개의 버텍스, $m$ 개의 에지를 가지면 $m \le 3n - 6$
• [2]: 모든 심플 평면 그래프 $G$ 는 $\deg v \le 5$ 인 버텍스 $v \in V(G)$ 를 가진다.

증명

[1]

평면 그래프의 각 페이스는 적어도 세 개의 에지로 둘러싸여있다고 하자.

가장 간단한 케이스로 컴플리트 그래프 $K_{3}$ 만 달랑 있다면 에지 $m=3$ 에 페이스 $f=2$ 고, 여기서 페이스가 하나 늘어나려면 적어도 두 개의 에지가 늘어야하므로 $3f \le 2m$ 이다.

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

오일러 공식에 따라, $f = m - n + 2$ 이므로 $$ 3(m-n+2) \le 2m $$ 정리하면 $m \le 3n - 6$ 을 얻는다.

■

[2]

$G$ 는 연결 그래프일 필요는 없지만 각각의 컴포넌트에 대해서만 확인하면 충분하다. 일반성을 잃지 않고, $G$ 는 연결 그래프고 적어도 $3$ 개의 버텍스를 가진다고 해보자. 귀류법을 사용하기 위해 $G$ 의 모든 버텍스의 차수가 $6$ 이상이라고 가정하자.

$G$ 의 버텍스의 수가 $n \ge 3$,에지의 수가 $m$ 이라고 하면 모든 버텍스의 차수가 $6$ 이상이므로 $$ 6n \le 2m $$ 양변을 $2$ 로 나누면 $3n \le m$ 인데, 정리 [1]에 따라 $$ 3n \le 3n - 6 $$ 이는 모순이므로, $\deg v \le 5$ 인 버텍스 $v \in V(G)$ 가 적어도 하나 존재해야한다.

■