꼭짓점의 차수와 변의 개수

동아리 첫 모임에 아홉 명이 왔다. 진행자가 "모두 정확히 세 명과 악수하세요"라고 했는데, 아무리 짝을 맞추어 보아도 누군가는 두 명이나 네 명과 악수하게 되었다. 열 명이었다면 문제없이 되었을 것이다. 사람을 꼭짓점, 악수를 변으로 그리면 각 사람이 악수한 횟수는 꼭짓점의 차수이다. 모든 사람의 악수 횟수를 더하면 어떤 수가 될까? 그리고 그 수에서 아홉 명의 계획이 불가능한 까닭을 알 수 있을까?

4.2.1변 하나가 차수 둘

변 하나는 두 꼭짓점을 이으므로, 그 두 꼭짓점의 차수를 하나씩 올린다. 그래서 모든 꼭짓점의 차수를 더하면 각 변이 정확히 두 번씩 세어져, 차수의 합은 변의 개수의 두 배이다. 이것을 악수 정리라 한다. 차수의 합은 늘 짝수이므로, 홀수 차수인 꼭짓점의 개수는 반드시 짝수이다. 홀수 차수가 홀수 개이면 그 합이 홀수가 되어, 짝수 차수들의 합과 더해도 전체가 홀수가 되기 때문이다.

아홉 명이 모두 세 명과 악수하면 차수의 합이 \(9\times3 = 27\)로 홀수인데, 이는 변의 개수의 두 배가 될 수 없다. 그래서 그런 그래프는 존재하지 않는다. 반면 열 명이면 합이 30이어서 변 15개의 그래프가 있을 수 있고, 실제로 만들 수도 있다. 이렇게 악수 정리는 어떤 그래프가 불가능하다는 것을 계산 한 번으로 보여 준다. 그러나 합이 짝수라는 것만으로 그래프가 꼭 있는 것은 아니다.¹

4.2.2차수 목록만 보고 판정하기

각 꼭짓점의 차수를 큰 순서로 늘어놓은 것을 차수열이라 한다. 차수열 \((3, 3, 3, 1)\)은 합이 10으로 짝수이지만, 이런 단순그래프는 없다. 단순그래프는 두 꼭짓점 사이에 변이 많아야 하나이고 자기 자신과 잇는 변이 없는 그래프이다. 차수 3인 꼭짓점 셋은 각각 나머지 세 점과 모두 이어져야 하는데, 그러면 넷째 점의 차수가 3이 되어야 하기 때문이다. 이런 판정은 가장 큰 차수의 꼭짓점을 그다음 큰 꼭짓점들과 이어 지우고, 남은 차수열로 같은 일을 되풀이해 한다.

4.2.3예제 풀이

모두 세 명과 악수하면 차수의 합이 27로 홀수여서 \(2m\)이 될 수 없으므로 불가능하다. 한 명만 네 명과 악수하면 합은 \(4 + 8\times3 = 28\)로 짝수이다. 합이 짝수인 것만으로는 충분하지 않지만, 차수열 \((4, 3, 3, 3, 3, 3, 3, 3, 3)\)을 그림 2의 방법으로 줄이면 음수 없이 일곱 점의 차수가 모두 2인 차수열이 되고, 이는 일곱 점을 원형으로 이은 그래프로 만들 수 있으므로 가능하다. 홀수 차수인 꼭짓점은 여덟 명으로 짝수 개이다.

차수열 \((3, 2, 2, 2, 1)\)은 합이 10이므로 변의 개수는 5이다. 그림 2처럼 차수열을 줄이면 음수 없이 끝나므로 그런 단순그래프가 있다. 예를 들어 꼭짓점 a를 b, c, d와 잇고, b와 c, d와 e를 이으면 차수가 \(3, 2, 2, 2, 1\)이 된다. 즉 차수의 합은 변의 개수의 두 배라는 악수 정리로 많은 그래프가 불가능함을 바로 보일 수 있고, 차수열이 가능한지는 차례로 줄여 가며 판정한다.

아래 탐구 카드에서 악수한 횟수의 합이 늘 짝수인지 확인해 보고, 차수 목록만 보고 그런 그래프가 있는지 판정해 보자.

1. 차수열을 차례로 줄여 판정하는 방법은 1955년 체코의 하벨과 1962년 미국의 하키미가 각각 찾아 하벨–하키미 알고리즘이라 부른다. 분자식에서 원자들이 몇 개의 결합을 가질 수 있는지 따지는 화학 문제에도 같은 생각이 쓰인다.