비징의 정리

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

비징의 정리에 따르면, (단순 무향) 그래프 ${\displaystyle \Gamma }$의 변 색칠수 ${\displaystyle \chi '(\Gamma )}$ 및 ${\displaystyle \Gamma }$의 최대 차수

${\displaystyle \Delta (\Gamma )=\max _{v\in V(\Gamma )}\Delta (v)}$

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

${\displaystyle \Delta (\Gamma )\leq \chi '(\Gamma )\leq \Delta (\Gamma )+1}$

이에 따라서, 모든 그래프는 다음과 같이 1종 그래프(영어: class 1 graph) 및 2종 그래프(영어: class 2 graph)로 분류된다.

• 1종 그래프의 경우 ${\displaystyle \chi '(\Gamma )=\Delta (\Gamma )}$이다.
• 2종 그래프의 경우 ${\displaystyle \chi '(\Gamma )=\Delta (\Gamma )+1}$이다.

이 정리는 다중 그래프에 대하여 성립하지 않는다.

에르되시-레니 모형(영어: Erdős–Rényi model)에서, ${\displaystyle n}$개의 꼭짓점을 갖는 무작위 그래프가 1종 그래프일 확률 ${\displaystyle p(n)}$은 다음과 같은 극한을 갖는다.^[1]

${\displaystyle \lim _{n\to \infty }p(n)=1}$

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

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

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

우크라이나의 수학자 바딤 게오르기예비치 비징(러시아어: Вади́м Гео́ргиевич Визинг, 우크라이나어: Вадим Георгійович Візінг 바딤 게오르기요비치 비징^[*])이 1964년에 증명하였다.^[4]

• “Vizing theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.