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 :)


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

  • $\begingroup$ Ok, but how to define problem in bipartite graph? And why $\Delta (G) $ is number of DIFFERENT way? $\endgroup$ – user180834 Dec 8 '14 at 21:43
  • 1
    $\begingroup$ 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? $\endgroup$ – JiK Dec 8 '14 at 21:46
  • $\begingroup$ "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 $\endgroup$ – user180834 Dec 8 '14 at 21:52
  • 1
    $\begingroup$ Now, what does the theorem say about the bipartite graph in your link? $\endgroup$ – JiK Dec 8 '14 at 21:54
  • $\begingroup$ Thanks, now everything become clear. $\endgroup$ – user180834 Dec 8 '14 at 22:13


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.