비징의 정리

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

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

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

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

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

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

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

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

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

 각주 

 외부 링크 


분류:그래프 색칠
분류:그래프 이론 정리