Classic Hand shake question

I am asked the following question:

My wife and I were invited to a party attended by four other husband-wife couples, making a total of ten people. As people arrived, there was some hand shaking. No one shook their own hand, and there were no husband-wife hand shakes. When it was over, I asked each person "How many people did you shake hands with?" I asked nine people (not including myself) and got nine different answers. How many people did my wife shake hands with?

Since there are 10 people in the room should I use the formula n(n-1)2, which results in 10(10-1)/2=45 which would be the sum of all the handshakes. If I divide that by ten I would get 4.5 people shook his wife's hand.

This doesn't seem correct at all. What is the right direction to head in order to solve this question?

EDIT:

I ended up trying to solve by pairing everyone together and drawing a graph showing the relations between everyone:

But this wasn't complete apparently.

-

Hint: No person shook more than eight hands, so you must have gotten answers from 0 to 8 inclusive. Who is married to the person who shook 8?

-
Did she shake 4 hands? – Nick Oct 3 '12 at 17:06
@Nick: yes, she did. – Ross Millikan Oct 3 '12 at 17:16
I do not see how she shook 4 hands. Why could no one have shaken 0 hands? He got answers from 0 to 8 inclusive right? – Moderat Nov 21 '12 at 18:10
@jmi4: yes, somebody shook 0 hands. The person who shook 8 had to shake with everybody except his/her spouse, who must be the person who shook 0. The the ones that shook 7 and 1 are married. It keeps going, with each couple summing to 8. That requires two 4's. To avoid getting two like answers, he must be one of the two and his wife the other. – Ross Millikan Nov 25 '12 at 23:11
@RossMillikan can you take a look at my edits. I didn't end up getting the answer the proper way could you expand on your answer so I can see the proper way. My full hw is [here][1] [1]:dl.dropbox.com/u/16641927/hw6.jpg – Nick Dec 12 '12 at 21:52

The answer lies in the question itself. It says, there were no hand shakes between husband-wife and the man asking everyone has not included himself in the count, so he and his wife would not be counted. Therefore the answer is 8...His wife shook hands with 8 people(excluding her husband).

-
Who shook 0 then? – Karolis Juodelė Oct 3 '12 at 17:37
No.if his wife shook 8 hands, she shook hands with everybody except her husband. Nobody shook 0 hands so there must be two people who shook the same number. – Ross Millikan Oct 3 '12 at 17:41
How? any explanation? – laique mehdi Oct 3 '12 at 17:44
Yes, you're right Ross – laique mehdi Oct 3 '12 at 17:46
It sounds like you are reading it that everybody shook all hands except their spouse's. Then each person would shake 8. But then when he asked how many hands people shook, all answers would be the same. – Ross Millikan Oct 3 '12 at 17:50