قضیه ویزینگ

در نظریه گراف، قضیه ویزینگ (به نام وادیم ویزینگ (به انگلیسی: Vadim G. Vizing) نامگذاری شده که آن را در سال ۱۹۶۴ منتشر کرد) بیان می کند که یال های هر گراف ساده را می توان با حداکثر یکی بیشتر از بیشترین درجه Δ رئوس گراف رنگ کرد.
اگر شبه جنگل P که به این روش ساخته می شود شامل یک مسیر از v به w باشد که هیچ یال خروجی در P نداشته باشد، آنگاه رنگ c وجود دارد که در هر دو u و w قابل استفاده است. رنگ آمیزی دوباره یال uw با رنگ c اجازه می دهد که رنگ های یال باقی مانده در طول مسیر یک گام انتقال یابند: برای هر رأس p در مسیر، یال up رنگی را که قبلاً توسط تالی p در مسیر استفاده شده بود را می گیرد. این منجر به یک رنگ آمیزی جدید می شود که شامل یال uv نیز هست.
از سوی دیگر، اگر مسیری که از v شروع می شود در شبه جنگل P منجر به یک دور شود، فرض کنید w همسایهٔ u در شبه جنگل P باشد در جایی که مسیر به دور می پیوندد، فرض کنید c رنگ یال uw باشد، و فرض کنید d رنگی باشد که توسط هیچکدام از یال های راس u استفاده نشده است. آنگاه جابجا کردن رنگ های c و d روی یک زنجیر کمپ (به انگلیسی: Kempe chain) یا دور را می شکند یا یالی که در آن مسیر به دور می پیوندد، منجر به حالت قبلی می شود.
همواره حداقل Δ رنگ لازم است، بنابراین گراف های ساده را می توان به دو رده افراز کرد: گراف های «ردهٔ اول» آنهایی هستند که Δ رنگ، برای رنگ آمیزی آن ها کافی است و گراف های «ردهٔ دوم» آن هایی هستند که Δ + ۱ رنگ، برای رنگ آمیزی آن ها لازم است.
هنگامی که Δ = ۱ است، گراف G خود یک تطابق است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی آن یک است. پس، تمام گراف های با Δ(G) = ۱ جزء گرافهای ردهٔ اول هستند.
هنگامی که Δ = ۲ است، گراف G اجتماع مجموعه های مجزای مسیرها و دورها است. اگر همهٔ دورها زوج باشند، آن ها می توانند ۲-رنگ پذیر یالی باشند با تغییر تناوبی دو رنگ، پیرامون هر دور. هر چند، اگر حداقل یک دور فرد وجود داشته باشد، هیچ ۲-رنگ آمیزی یالی ممکن نیست. پس، یک گراف با Δ = ۲ جزء گراف های ردهٔ اول است اگر و تنها اگر دوبخشی باشد.