Another big party

[Exploited]

Yeah that's what I call a great party - lots of girls, lots of boys, lots of dancing! Tough night with lots of fun!

After the party it came up that there is no such boy on the whole party that danced with all girls. At the same time it came up that every girl danced with at least one boy.
Please proof that you can find at least two dancing couples M1+G1 and M2+G2 for which:
- M1 did not danced with G2
- M2 did not danced with G1

[Joka X]

Arrrghhhhh!!!!!!!!!

[motomaniacs]

make me more bald:(

[Exploited]

I will do it then:

We will take M1, which is the man, who danced with most of the girls around and let's choose D2 - one of the ladies, with which M1 DID NOT DANCED. However D2 danced with at least one man - this will be M2. These three exists for sure as you can see. Now let we see if the lady D1 exists.
We will start on the other way - let we assume that D1 do not exist => M2 danced with all girls with which M1 danced + one more lady (D2)... but at the same time we have that M1 danced with MOST of the girls => it is impossible => D1 exist
=> (M1, D1) and (M2, D2) exist