# Boys, girls. Solve problem using edge-colouring.

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.

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$.

• Ok, but how to define problem in bipartite graph? And why $\Delta (G)$ is number of DIFFERENT way? – user180834 Dec 8 '14 at 21:43
• You have boys and girls, and some boys and girls know each other (I understand that if a boy $x$ knows a girl $y$, then $y$ also knows $x$, am I right?). How would you express this as a bipartite graph? – JiK Dec 8 '14 at 21:46
• "I understand that if a boy x knows a girl y, then y also knows x, am I right?" I understand it the same. And my interpretation: i.imgur.com/Zs6Fm2m.jpg @JiK, please glance: math.stackexchange.com/questions/1057889/colouring-graphs-edges – user180834 Dec 8 '14 at 21:52
• Now, what does the theorem say about the bipartite graph in your link? – JiK Dec 8 '14 at 21:54
• Thanks, now everything become clear. – user180834 Dec 8 '14 at 22:13

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$

• dtldarek@ Are you from Poland :)? – user180834 Dec 8 '14 at 22:08
• @user180834 Indeed I am, how do you know? – dtldarek Dec 8 '14 at 22:14
• I am also and your name is dtlDAREK :) – user180834 Dec 8 '14 at 22:17
• @Darek, could you help here? :)math.stackexchange.com/questions/1057889/colouring-graphs-edges – user180834 Dec 8 '14 at 22:27
• Well, you are very perceptive, graph theory should't be any problem, good luck to you :-) – dtldarek Dec 8 '14 at 22:28