What is the minimum number of handshakes at a party with eight people?

[Ackbach]

Here is this week's problem:

-----

Eight total people (four couples), including the host and hostess, arrive at a party, and a number of handshakes occur. No one shakes hands with their own spouse or with themselves, and everyone shakes at least one hand. The host asks the others how many hands they shook, and everyone (except possibly the hostess) gives a different answer. The hostess is the last to answer; what is the smallest possible number of hands she shook?

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to Fallen Angel for a correct solution, which you can read below:

Spoiler

At first, we got 6 different answer (from the couples that aren't host), which is a number from 1 to 6 (bacause no one can shake itself or it's couple and everybody shakes at least once), so all this numbers are someone's answer.

Claim: Hostess just need to shake once.

Proof:

Let $\{m_1,m_2,m_3,f_1,f_2,f_3,\text{host},\text{hostess}\}$ be the vertex of a graph where $m_i-f_i$ is a couple, then we can got the following edges (that means shaking hands).

$\{(\text{host},m_1),(\text{host},m_2),(\text{host},m_3),(\text{host},f_3),(m_1,m_2),(m_1,m_3),(m_1,\text{hostess}),(m_1,f_3),(m_1,f_2),(m_2,m_3),(m_2,f_3),(m_2,f_1),(m_3,f_2)\}$

and we are done because $\deg(m_i)=7-i$, $\deg(f_{i})=i$, $\deg(\text{host})=4$ and $\deg(\text{hostess})=1$.