After the "8 must be paired with 0" step, my next step was to say, "Now, there is someone who shook hands with 7 people. We know he didn't shake hands with Mr.

After the "8 must be paired with 0" step, my next step was to say, "Now, there is someone who shook hands with 7 people. We know he didn't shake hands with Mr. 0, so he must have shaken hands with everyone else except his wife. Meanwhile, there's also someone who shook hands with 1 person, and we already know he shook with Mrs. 8, so he must have not shaken hands with anyone else. Therefore, 7 and 1 must be a couple." Then, accounting for the shakings with 7 and 8 and the non-shakings with 0 and 1, we similarly see that 2 can't have shaken hands with anyone else, but 6 must have shaken hands with everyone else except his partner, so 2 and 6 must be paired as well. The 5-3 pairing follows too, after which we're left with 4 and the question-asker, who are a couple by process of elimination. Incidentally, we conclude that the question-asker also shook hands with 4 people: Mrs. 8, 7, 6, and 5.