= Solution
{c}
Use <mathematical induction> on the <maximum degree> $\Delta$, including $\Delta=0$ as the base case. A <graph> of <maximum degree> zero has no <edges>, so zero colours suffice.
For $\Delta>0$, part (ii) supplies a <matching in a graph> $M$ meeting every <vertex> of <vertex degree> $\Delta$. Delete its <edges>, retaining all <vertices>. Each <vertex> formerly of <maximum degree> loses one incident <edge>; every other <vertex> already had <vertex degree> at most $\Delta-1$. Hence
$$
\Delta(G-M)\leq\Delta-1.
$$
The resulting <graph> is still a <bipartite graph>. By <mathematical induction>, it has a <proper edge colouring> using at most $\Delta-1$ colours. Give every <edge> of $M$ one new colour. Since $M$ is a <matching in a graph>, this produces a <proper edge colouring> of $G$ with at most $\Delta$ colours. The <edges> at a <vertex> of <maximum degree> require at least $\Delta$ colours, so
$$
\boxed{\chi'(G)=\Delta.}
$$
This is <Kőnig's line colouring theorem>.
Back to article page
