= Kőnig's line colouring theorem
{c}
{title2=$\chi'(G)=\Delta(G)$}
For every finite <bipartite graph>, the <edge chromatic number> equals its <maximum degree>. Repeatedly remove a <matching covering maximum-degree vertices in a bipartite graph>: each removal reduces the <maximum degree> by at least one. The removed <matchings in a graph> are colour classes of a <proper edge colouring>. The reverse bound follows from the distinct colours required at a <vertex> of <maximum degree>.
Back to article page
