Edge Coloring

Imagine a school timetable. Each lesson pairs one teacher with one class, and a teacher can't be in two rooms at once. Draw teachers and classes as dots, lessons as lines between them, and the question becomes: how few time slots do you need so that no teacher (and no class) has two lessons at the same time?

That is exactly edge coloring: assign a color to every edge of a graph so that no two edges meeting at the same vertex share a color. The smallest number of colors you can get away with is called the chromatic index.

One quantity dominates the answer. Let Δ (the maximum degree) be the largest number of edges touching any single vertex. You obviously need at least Δ colors — those Δ edges all meet at one point and must differ. The astonishing fact is how close to Δ you can always get.

Below is a small graph. Pick a color, then click an edge to paint it. The rule: two edges that touch the same dot must never share a color. The panel tracks Δ for this graph and tells you the moment any pair of adjacent edges clashes.

<p class="hint">{{hint}}</p>
<div class="palette" id="palette"></div>
<svg id="graph" viewBox="0 0 320 240" aria-label="{{aria_graph}}"></svg>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.palette { display: flex; gap: .5rem; margin: .3rem 0 .5rem; }
.swatch { width: 30px; height: 30px; border-radius: 50%; cursor: pointer;
          border: 3px solid transparent; }
.swatch.sel { border-color: #1d3557; }
svg { width: 100%; max-width: 360px; height: auto; display: block; background: #f6f8fa;
      border-radius: 10px; }
.edge { stroke: #b9c2cc; stroke-width: 7; cursor: pointer; stroke-linecap: round; }
.edge.clash { stroke-dasharray: 6 5; }
.node { fill: #1d3557; }
.nlabel { fill: #fff; font: 700 13px system-ui, sans-serif; text-anchor: middle;
          dominant-baseline: central; pointer-events: none; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Try to use as few colors as possible. You will find Δ colors is usually enough — and when it isn't, one extra color always finishes the job. Press Auto-color to watch a greedy pass assign colors edge by edge, never using more than Δ+1.

Here is one of the most elegant results in graph theory.

• Vizing's theorem (Vadim Vizing, 1964). Every simple graph has chromatic index equal to either Δ or Δ+1 — there is no third option. A whole problem squeezed into two values.
• The upper bound is constructive and easy. Vizing's proof is an algorithm: it colors any graph with at most Δ+1 colors in polynomial time (using "fans" and "alternating paths"). So you never need to search — a near-optimal coloring is always within reach.
• The hard part is the gap. Graphs needing exactly Δ are called Class 1; those needing Δ+1 are Class 2. Deciding which class a graph belongs to is NP-complete — Ian Holyer (1981) proved it, even for the restricted case of 3-regular (cubic) graphs, by encoding 3-SAT into the coloring.
• So the landscape splits cleanly. Getting within one color of optimal is a polynomial-time guarantee; squeezing out that last color is as hard as anything in NP.

That mix is the charm of edge coloring. Vizing hands you an almost-perfect answer for free, yet the final yes/no — Δ or Δ+1? — lands squarely in the world of P vs NP.

Edge coloring is the mathematics of conflict-free scheduling — whenever two tasks share a resource and can't run together, they're adjacent edges that need different colors:

• Timetabling. Teacher–class lessons become edges; each color is a time slot, so a proper coloring is a clash-free schedule using as few periods as possible.
• Sports tournaments. A round-robin where every team plays every other is the complete graph; an edge coloring packs all matches into the fewest rounds.
• Network switching. In a crossbar switch, simultaneous input–output connections that share a port conflict; each color is one switching phase.
• Frequency and link assignment. Communication links meeting at a node must use distinct channels — exactly a proper edge coloring.

Each color class is just a matching — a set of edges with no shared endpoint — so edge coloring is really "partition all edges into the fewest matchings," a cousin of graph coloring on the line graph.

Edge coloring sits in a rare sweet spot. Vizing's theorem guarantees the answer is always Δ or Δ+1, and a polynomial-time algorithm hands you a coloring with at most Δ+1 colors — almost optimal, every single time, for free.

And yet the final question — is this graph Class 1 or Class 2? — is NP-complete (Holyer, 1981). The same problem is simultaneously a textbook example of how good an approximation can be and how stubborn the exact answer remains. One color is all that separates the easy world from P vs NP.