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

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

Proof of diracs Theorem

정리 1

$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$ 가 해밀톤 그래프가 아니라는 가정에 모순이 된다.


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

댓글