Introduction

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.

Color the Edges

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">Pick a color, then click an edge to paint it. The rule: two edges that meet at the same dot must never share a color. This graph has maximum degree <b>Δ = 3</b>, so with luck you can finish in 3 colors. Checking is instant; the last color can be the hard one.</p>
<div class="palette" id="palette"></div>
<svg id="graph" viewBox="0 0 320 240" aria-label="graph"></svg>
<div class="status" id="status">Pick a color and start painting.</div>
<div class="btns">
  <button id="auto" type="button">Auto-color</button>
  <button id="reset" type="button" class="ghost">Clear</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Edge coloring: paint every edge so that two edges sharing a vertex never share a color. The fewest colors needed is the chromatic index. Vizing's theorem (1964) proves it is always Δ or Δ+1, and a greedy/constructive pass reaches Δ+1 in polynomial time. This graph is K4: Δ = 3 and it is colorable with 3.
const NS = 'http://www.w3.org/2000/svg';
const COLORS = ['#e63946', '#2a9d8f', '#e9c46a', '#5a4fcf'];
const NAMES = ['red', 'teal', 'amber', 'violet'];
// K4 vertices on a square.
const NODES = [ {x:60,y:55}, {x:260,y:55}, {x:260,y:185}, {x:60,y:185} ];
// All 6 edges of K4 (pairs of vertex indices).
const EDGES = [ [0,1],[1,2],[2,3],[3,0],[0,2],[1,3] ];
let sel = 0;                       // selected palette color
const color = EDGES.map(() => -1); // -1 = uncolored

function degree(){ // max degree Δ
  const deg = NODES.map(() => 0);
  for (const [a,b] of EDGES){ deg[a]++; deg[b]++; }
  return Math.max(...deg);
}
const DELTA = degree();

// Two edges are adjacent iff they share a vertex.
function adjacent(i,j){
  const [a,b] = EDGES[i], [c,d] = EDGES[j];
  return a===c||a===d||b===c||b===d;
}
// Indices of adjacent edges that clash (same color) with edge i.
function clashesOf(i){
  if (color[i] < 0) return [];
  const out = [];
  for (let j=0; j<EDGES.length; j++)
    if (j!==i && adjacent(i,j) && color[j]===color[i]) out.push(j);
  return out;
}
function anyClash(){
  for (let i=0;i<EDGES.length;i++) if (clashesOf(i).length) return true;
  return false;
}
function usedColors(){ return new Set(color.filter(c => c>=0)).size; }

function buildPalette(){
  const p = document.getElementById('palette'); p.innerHTML='';
  COLORS.forEach((c,i)=>{
    const s=document.createElement('div');
    s.className='swatch'+(i===sel?' sel':''); s.style.background=c;
    s.title=NAMES[i];
    s.addEventListener('click',()=>{ sel=i; buildPalette(); });
    p.appendChild(s);
  });
}

function render(){
  const g=document.getElementById('graph'); g.innerHTML='';
  EDGES.forEach((e,i)=>{
    const [a,b]=e;
    const ln=document.createElementNS(NS,'line');
    ln.setAttribute('x1',NODES[a].x); ln.setAttribute('y1',NODES[a].y);
    ln.setAttribute('x2',NODES[b].x); ln.setAttribute('y2',NODES[b].y);
    const clash = clashesOf(i).length>0;
    ln.setAttribute('class','edge'+(clash?' clash':''));
    if (color[i]>=0) ln.style.stroke=COLORS[color[i]];
    ln.addEventListener('click',()=>{
      color[i] = (color[i]===sel) ? -1 : sel; // click same color again to clear
      render(); updateStatus();
    });
    g.appendChild(ln);
  });
  NODES.forEach((n,i)=>{
    const c=document.createElementNS(NS,'circle');
    c.setAttribute('cx',n.x); c.setAttribute('cy',n.y); c.setAttribute('r',16);
    c.setAttribute('class','node'); g.appendChild(c);
    const t=document.createElementNS(NS,'text');
    t.setAttribute('x',n.x); t.setAttribute('y',n.y); t.setAttribute('class','nlabel');
    t.textContent=String.fromCharCode(65+i); g.appendChild(t);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function updateStatus(){
  const left = color.filter(c=>c<0).length;
  if (anyClash()){ setStatus('✗ Two touching edges share a color. Fix the clash.','bad'); return; }
  if (left>0){ setStatus(fmt('No clashes so far — %left% edge(s) still uncolored.', { left: left }),''); return; }
  setStatus(fmt('✓ Proper coloring with %usedColors% colors (Δ = %DELTA%).', { usedColors: usedColors(), DELTA: DELTA }),'ok');
}

// Greedy edge coloring: for each edge, use the smallest color not used by any adjacent edge. Vizing guarantees this never needs more than Δ+1 colors.
function autoColor(){
  color.fill(-1);
  for (let i=0;i<EDGES.length;i++){
    const used=new Set();
    for (let j=0;j<EDGES.length;j++)
      if (j!==i && adjacent(i,j) && color[j]>=0) used.add(color[j]);
    let c=0; while (used.has(c)) c++;
    color[i]=c;
  }
  render();
  const k=usedColors();
  setStatus(fmt('✓ Greedy coloring used %k% colors — at most Δ+1 = %DELTA%%v%.', { k: k, DELTA: DELTA, v: 1 }),'ok');
  console.log('Greedy edge coloring:', color.map(c=>NAMES[c]).join(', '),
              '| colors used:', k, '| Δ =', DELTA);
}
document.getElementById('auto').addEventListener('click',autoColor);
document.getElementById('reset').addEventListener('click',()=>{ color.fill(-1); render(); updateStatus(); });
buildPalette(); render(); updateStatus();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/edge-coloring/Content licensed under CC BY-NC 4.0.