📂그래프이론

그래프 이론에서의 디락 정리 증명

정리 ¹

$G$ 가 $n ( \ge 3)$ 개의 버텍스를 가진 심플 그래프라고 하자.

• [1] 디락 정리: $G$ 의 모든 버텍스 $v$ 에 대해 $\deg (v) \ge n / 2$ 면 $G$ 는 해밀톤 그래프다.
• [2] 오레 정리: $G$ 의 모든 인접하지 않은 두 버텍스의 쌍 $(v ,w)$ 에 대해 $\deg (v) + \deg(w) \ge n$ 면 $G$ 는 해밀톤 그래프다.

설명

디락 정리는 해밀톤 그래프의 동치조건까지는 아니지만 어떤 경우에 충분히 해밀톤 그래프인지를 판별해내는 정리다. 이러한 사실은 1952년 증명되었다가 1960년 오레^ore에 의해 일반화되었으나, 여전히 디락 정리의 입지가 높아 오레 정리의 따름 정리로써 남게 되었다.

증명

전략: 오레 정리가 디락 정리를 함의한다는 것은 너무나 자명하므로 오레 정리만 증명하면 충분하다. 귀류법으로 $G$ 에서 에지를 $m$ 개 추가해도 해밀톤 그래프임을 보이고, 수학적 귀납법을 통해 에지를 $m , m -1 , \cdots , 1 , 0$ 개만 더해도 해밀톤 그래프가 됨을 보여서 결국 $G$ 가 해밀톤 그래프라는 결론을 이끌어낸다.

[2]

$\deg (v) + \deg(w) \ge n$ 인데 $G$ 가 해밀톤 그래프가 아니라고 가정해보자. $$ v_{1} \to \cdots \to v_{n} $$ $n$ 개의 버텍스 $v_{1} , \cdots , v_{n} \in V(G)$ 에 대해 몇 개의 에지를 추가한 그래프 $H$ 에서는 위와 같이 모든 버텍스를 지나는 패스를 만들 수 있을 것이다. 단 $v_{1}$ 와 $v_{n}$ 를 잇는 에지 하나만 없어서 사이클이 아니고 $H$ 역시 해밀톤 그래프가 아니라고하자. 물론 $H$ 는 에지를 추가해 차수가 늘어났을 뿐이기 때문에 원래 $G$ 에서 만족하던 $$\deg (v) + \deg(w) \ge n$$ 에 위배되지는 않는다. 또한 $v_{1}$ 와 $v_{n}$ 은 인접하지 않으므로 $$\deg (v_{1}) + \deg(v_{n}) \ge n$$ 이다. $v_{1}$ 와 $v_{n}$ 의 차수의 합이 전체 버텍스보다 많다는 것은 $v_{1}$ 와 $v_{i}$ 가 인접하면서 $v_{n}$ 과 $v_{i-1}$ 이 인접하게끔 하는 자연수 $2 \le i \le n$ 가 존재한다는 것이다. 그러면 다음과 같은 사이클이 존재해야한다. $$ v_{1} \to v_{2} \to \cdots \to v_{i-1} \to v_{n} \to v_{n-1} \to \cdots \to v_{i+1} \to v_{i} \to v_{1} $$ 이는 $H$ 가 해밀톤 그래프가 아니라는 것에 모순이다. 이러한 논의는 $G$ 에서 추가되었으면서 $H$ 의 해밀톤 사이클에 포함된 에지를 하나 지워서 새로운 그래프 $h '$ 를 만들어도 똑같이 적용될 수 있고, 결국 $G$ 가 해밀톤 그래프가 아니라는 가정에 모순이 된다.

■