Edge colouring

Let be a graph. An edge colouring of is a function such that for every pair of distinct edges such that and share a vertex.

If is a finite Bipartite graphBipartite graph, then the minimum number of colours needed for an edge colouring of is the maximum DegreeDegree of .

Proof:
Clearly an edge colouring is not possible with fewer colours than the maximum degree of , since all edges of the vertex with that degree must have distinct colors. Left to prove is that it is always possible to colour with that many colours. We induce on . If , then we clearly only need one colour.

Now take a bipartite graph with edges and maximum degree . Take any edge and consider with . Clearly is also a bipartite graph, whose maximum degree is either or . By our induction hypothesis, we know this can be coloured with at most colours. Since we removed the edge , we know , meaning there is a colour in the graph, not used among the edges of , and a colour in the graph, not used among the edges of . If we can choose we can give this colour to and we are done.

Otherwise, we show that we can modify the colouring of to do this. In this case, we hence know that has an edge with colour to a node . Instead, colour that edge , and if already had an edge with colour , colour that , and if the neighbour already had an edge with colour , colour that , and so on. Since is finite and bipartite, this process will stop, and we know it will not stop at since that would imply has an edge with colour . This now means no longer has an edge with colour , meaning we can colour with and we are done.