The existence of two couples of dancers that did not exchange partners

At a homecoming dance, no boy dances with every girl, but each girl dances with at least one boy. Prove that there are two couples, gb and g'b', who dance, such that g doesn't dance with b' and g' doesn't dance with b.

I'm not sure where to start. Hints only please, NO SOLUTIONS. I will most likely reply back to your hint to ask you more, so please stay online :)

• Here was the hint given: Use the extremal principle: start with the boy who dances with the most girls. Oct 18, 2014 at 3:12
• So, if we choose the boy, we'll call $b$, who danced with the most girls, pick one of them that he danced with, call her $g$. We want to pick a $b,g,b',g'$ satisfying the conditions, so who might we choose for $g'$ and why does she exist? What can we say about the dance partners of $g'$? Oct 18, 2014 at 3:20
• It takes 2 to tango. Oct 18, 2014 at 3:21
• @JMoravitz This is what I have so far. I used the hint that the problem gave me and the hint that you gave me. So let's say that there are m boys and n girls. Since no boy dances with every girl, the max case that we can use is that one boy dances with n-1 girls. So let's call this boy Alan. Since each girl dances with at least one boy, and we have one girl left (call her Sally), she needs to dance with a boy that's not Alan. This boy is called Jim. So now we have our two couples: 1. Jim and Sally 2. Alan and any one of the girls who are not Sally . What can I do next to continue this problem? Oct 18, 2014 at 3:41
• continuing below so I can use pictures Oct 18, 2014 at 3:48

Let $b$ be the boy who danced with the most girls, we have our $b$ and our $g'$ and our $b'$ selected. We chose $g'$ to a girl who $b$ didn't dance with.

$b'$ is set as a boy that $g'$ danced with. It is possible that $b'$ danced with some of the girls that $b$ did. How many of them could he have danced with though? All of them? Why or why not?

When I made the picture, I didn't see that you decided to start using a variable $n$. the $n$ in my picture has nothing to do with the number of girls total, but rather the number of girls that $b$ danced with.

Also of importance, is that in your wordings where you say "there is one girl left", it wasn't guaranteed that our most popular boy danced with $n-1$ girls, that is merely an upper bound. It is more correct to say "there is at least one girl left", and "she danced with at least one boy"

• To make it easier, I'll just refer to b, our most popular boy, as "Bob" and b' as "Jerry". Since the rule is that no boy can dance with every girl, so Jerry can dance with his girl (g', call her Gina) and all of the girls that Bob has danced with except 1. I'm using the extreme/max case here, where Bob dances with as many girls as possible. Oct 18, 2014 at 19:35
• The only time I would use the statement that no boy dances with every girl is when showing that theres a girl, Gina ($g'$), who didn't dance with our most popular boy, Bob ($b$). So, Gina danced with at least one person, namely Jerry ($b'$). So did Jerry dance with all of Bob's partners? If he did, then who was the real most popular boy, Jerry or Bob? Oct 18, 2014 at 19:44
• Would it be Jerry? Since he danced with Gina, and all of Bob's partners? Oct 18, 2014 at 19:53
• Yes, but at the beginning, we said that Bob was the most popular though. So what does that tell us about the number of Bob's partners that Jerry danced with? Oct 18, 2014 at 19:54
• So then it is a contradiction.... so that means that Jerry CAN'T dance with ALL of Bob's partners? Oct 18, 2014 at 19:56

Use the extremal principle: start with the boy who dances with the most girls. Which girl didn't he dance with? Who danced with that girl?

Doin that, you will find your $b,b',g,g'$.