Vizing's theorem

Imagine you have many lines to color. You want to use few colors. You must color them so no two lines at one spot have the same color.

A man named Vadim Vizing found a rule for this. He found that you only need a few colors. You need no more than one extra color than the most lines at one spot.

Some groups of lines are called class one. These use the smallest number of colors. Other groups are called class two. These need one more color.

Other people found this rule too. A man named R. P. Gupta found it on his own.

This rule helps us understand how to color shapes.

Imagine you have a group of dots connected by lines. In math, we call this a graph. You want to color every line. There is one rule: no two lines meeting at the same dot can have the same color.

Vadim Vizing found a way to know how many colors you need. First, look at the busiest dot. Count how many lines meet there. This number is the maximum degree. Vizing's theorem says you only need one more color than that number.

We can split graphs into two groups. Class one graphs use only the number of colors from the busiest dot. Class two graphs need one extra color.

Vadim Vizing published this in 1964. An Indian mathematician named R. P. Gupta found it too. He found it while working on his doctorate.

Some graphs are easier to color than others. For example, a simple loop with an odd number of lines is class two. Most graphs are actually class one. This means they are easy to color with the smallest amount of colors.

Imagine you have a collection of dots connected by lines. In math, we call this a graph. You might want to color every line in your graph. However, you must follow one strict rule. No two lines that meet at the same dot can share a color. This is called edge coloring. To do this, you first find the busiest dot in your graph. We call the number of lines at that dot the maximum degree.

Vadim Vizing discovered a clever rule about these colors. His theorem says you never need many colors. You only need at most one more color than the maximum degree. This means the number of colors is very predictable. Because of this, we can sort graphs into two groups. Class one graphs use only the number of colors from the busiest dot. Class two graphs are a bit harder and need one extra color.

This discovery happened in the 1960s. Vadim Vizing was a Soviet mathematician working in Novosibirsk. He published his work in 1964. At the same time, an Indian mathematician named R. P. Gupta found it too. Gupta was working on his doctorate between 1965 and 1967. Vizing's original paper appeared in a journal called Diskret. Analiz. It was a somewhat obscure place for such a big idea.

Some graphs are much simpler than others. If a graph has no two lines touching, it is class one. If a graph is made of paths and even cycles, it is also class one. But an odd cycle, like a triangle, is class two. This is because you cannot alternate two colors around an odd shape. Most graphs in the world are actually class one. In a model of random graphs, the chance of being class one goes up as the graph gets bigger.

Mathematicians still study these patterns today. There is a famous idea called the planar graph conjecture. It looks at graphs that can be drawn without lines crossing. It suggests that most of these are class one. Finding the right colors is also a job for computers. While finding the perfect number of colors is a very hard task, Vizing's own method works quickly. It uses a way of changing colors to fill in the graph step by step.

In the field of graph theory, mathematicians often study how to assign properties to the components of a graph. One fascinating challenge is edge coloring. In this task, you must assign a color to every edge in a graph. The primary rule is that no two edges sharing a common vertex can have the same color. This prevents any color from appearing twice at a single point. To understand how many colors are required, we first look at the maximum degree, denoted as Δ. The maximum degree is the highest number of edges connected to any single vertex in the graph.

Vizing's theorem provides a precise limit for this coloring process. It states that every simple undirected graph can be edge colored using at most Δ + 1 colors. This means the number of colors needed is never more than one greater than the maximum degree. Because the number of colors must be at least Δ to satisfy the busiest vertex, Vizing's theorem creates a natural division. Graphs that can be colored using exactly Δ colors are called class one graphs. Graphs that require Δ + 1 colors are known as class two graphs.

The mechanics of the theorem are rooted in the relationship between missing colors and paths. A color is considered "missing" at a vertex if no edge connected to that vertex uses that color. The proof of the theorem often uses induction on the number of edges. If we have a properly colored graph and add a new edge, we must find a way to color it without violating the rules. This might involve finding a specific path of alternating colors, known as a Kempe chain. By swapping colors along these paths, we can rearrange the existing coloring to make room for the new edge.

The history of this theorem involves simultaneous discovery in different parts of the world. Vadim G. Vizing, a Soviet mathematician, published his result in 1964 while working in Novosibirsk. His work was inspired by a theorem by Vadim Vizing regarding multigraphs, which are graphs that can have multiple edges between the same two vertices. While Vizing's theorem applies to simple graphs, a more general version exists for multigraphs. This version states that a multigraph without loops can be colored with at most Δ + μ colors, where μ is the multiplicity of the edges. Meanwhile, Indian mathematician R. P. Gupta independently discovered the same result while completing his doctorate between 1965 and 1967.

Specific types of graphs follow predictable patterns. For example, if a graph has a maximum degree of one, it is simply a matching where no edges touch, making it class one. If the maximum degree is two, the graph consists of paths and cycles. Even cycles are always class one because you can alternate two colors perfectly. However, odd cycles, such as a triangle, are always class two because the alternating pattern fails at the end. Interestingly, in the Erdős–Rényi model of random graphs, the probability that a graph is class one approaches one as the number of vertices increases toward infinity.

Mathematicians have also explored how graph structure affects these classes. For instance, if the vertices with the maximum degree form an independent set, the graph is class one. There is also a famous conjecture regarding planar graphs, which are graphs that can be drawn without any edges crossing. Vizing conjectured that all simple planar graphs with a maximum degree of six or seven are class one. While it has been proven that planar graphs with a degree of at least eight are class one, the case for degree six remains unsolved. This connection to planarity links Vizing's work to the famous four color theorem.

Finally, the theorem has significant implications for computer science and algorithms. Determining whether a general graph is class one or class two is an NP-complete problem. This means there is no known way for a computer to solve it quickly for all possible graphs. However, Vizing's original proof is actually algorithmic. It provides a polynomial-time method to color any graph using at most Δ + 1 colors. Modern researchers have refined these methods. In 2024, new probabilistic quasilinear time algorithms were developed, offering even faster ways to handle large-scale coloring tasks.