📂그래프이론

악수 렘마 증명

Proof of handshaking Lemma

정리 ¹

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

설명

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

증명

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

■

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

따름정리

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