Boys, girls. Solve problem using edge-colouring.

Question

In a class each boy knows precisely $d$ girls and each girl knows precisely $d $ boys. Use a result on edge-colouring to show that the boys and girls can be paired off in friendly pairs in at least $d$ different ways.

Please help :)

Answer 1

A theorem: In this MSE question, it is shown that a bipartite graph $G$ has an edge coloring with $\Delta(G)$ colors, where $\Delta(G)$ is the maximal degree of $G$.

Answer 2

Hint:

• If you put boys on one side and girls on the other you will get a bipartite $d$-regular graph.
• By counting the edges you will get that the number of boys and girls is the same.
• Using the Hall's theorem you will get a perfect matching.
• Remove the above matching from the graph to get a $(d-1)$-regular graph.
• Repeat until you have $d$ disjoint matchings, color each using a different color.
• Use induction to formalize the above.
• There is related question here.

I hope this helps $\ddot\smile$