비징의 정리

그래프 이론에서 비징의 정리(Визинг의定理, )는 그래프의 변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다.

정의 
비징의 정리에 따르면, (단순 무향) 그래프 의 변 색칠수  및 의 최대 차수

사이에 다음과 같은 관계가 성립한다.

이에 따라서, 모든 그래프는 다음과 같이 1종 그래프() 및 2종 그래프()로 분류된다.
 1종 그래프의 경우 이다.
 2종 그래프의 경우 이다.
이 정리는 다중 그래프에 대하여 성립하지 않는다.

성질 
에르되시-레니 모형()에서, 개의 꼭짓점을 갖는 무작위 그래프가 1종 그래프일 확률 은 다음과 같은 극한을 갖는다.

즉, 에르되시-레니 모형에서 거의 모든 그래프는 1종 그래프이다.

최대 차수가 7 이상인 평면 그래프는 1종 그래프이다. 이 정리는 최대 차수가 8 이상인 경우는 비징이 증명하였고, 7인 경우는 2001년에 증명되었다. 최대 차수가 5 이하인 경우, 2종 평면 그래프가 존재하며, 이러한 그래프들은 정다면체로부터 작도할 수 있다. 최대 차수가 6인 경우는 미해결 문제로 남아 있다.

쾨니그의 정리에 따라, 모든 이분 그래프는 1종 그래프이다.

역사 
우크라이나의 수학자 바딤 게오르기예비치 비징(, )이 1964년에 증명하였다.

참고 문헌

외부 링크 
 

그래프 색칠
그래프 이론 정리