악수 렘마 증명

악수 렘마 증명

정리 1

임의의 그래프에서, 모든 버텍스의 차수의 합은 짝수다.

설명

이름의 ‘악수’는 보다시피 각각의 버텍스가 인접한 버텍스와 악수를 한다고 했을 때, 그 횟수가 바로 차수의 합이기 때문에 붙은 것이다.

증명

그래프 $G$ 에 대해 모든 차수의 합은 정확하게 모든 에지의 수의 두 배여야하므로 $$ \sum_{v \in V(G)} \deg (v) = 2 \left| E(G) \right| $$

위의 증명에서 차수가 홀수인 버텍스가 홀수개만큼 존재한다고 가정해보면 모든 버텍스의 차수의 합은 짝수인데, 이는 악수 렘마에 위배된다. 이에 따라 다음의 따름 정리를 얻는다.

따름정리

임의의 그래프에서, 차수가 홀수인 버텍스는 짝수개만큼만 존재해야한다.


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

댓글