악수 렘마 증명
Proof of handshaking Lemma
정리 1
임의의 그래프에서, 모든 버텍스의 차수의 합은 짝수다.
설명
이름의 ‘악수’는 보다시피 각각의 버텍스가 인접한 버텍스와 악수를 한다고 했을 때, 그 횟수가 바로 차수의 합이기 때문에 붙은 것이다.
증명
그래프 $G$ 에 대해 모든 차수의 합은 정확하게 모든 에지의 수의 두 배여야하므로 $$ \sum_{v \in V(G)} \deg (v) = 2 \left| E(G) \right| $$
■
위의 증명에서 차수가 홀수인 버텍스가 홀수개만큼 존재한다고 가정해보면 모든 버텍스의 차수의 합은 짝수인데, 이는 악수 렘마에 위배된다. 이에 따라 다음의 따름 정리를 얻는다.
따름정리
임의의 그래프에서, 차수가 홀수인 버텍스는 짝수개만큼만 존재해야한다.
-
Wilson. (1970). Introduction to Graph Theory: p12. ↩︎
댓글