The edges of any simple graph can be properly colored using either the maximum vertex degree or one more than the maximum vertex degree, and never more, colors. Proved by Vadim Vizing, it is the foundational result of edge-coloring theory, splitting graphs cleanly into two classes.
Facts
StatementVizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree of the graph. 1 Classification
Statement Form Statement Form Connections
Has Statement Form
In Branch
Proved By
Source Vizing's Theorem (Wikipedia)
Sources
1. Vizing's Theorem (Wikipedia)
Wikimedia Foundationlead paragraph, opening sentence
In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ of the graph.
lead paragraph, sentence naming the publication year
The theorem is named for Vadim G. Vizing who published it in 1964.
Proved By: Vadim G. Vizing, Lead section
Vizing who published it in 1964.
In Group: Graph Theory, Lead section
In graph theory, Vizing's theorem states that every simple undirected
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.