I am reading Eulerian graphs from this pdf. In page 210, exercise 9.5.7, I am stuck at following problem.
Each of 8 persons in a room has to hand shake with every other person as per the following rules:(a) The handshakes should take place sequentially. (b) Each handshake (except the first) should involve someone from the previous handshake. (c) No person should be involved in 3 consecutive handshakes.
Is there a way to sequence the handshakes so that these conditions are all met?
What I understand that is we have to convert this problem into graph theoretical notion and then it may be easy to solve. So I consider each person as a vertex and each hand shake as an edge.
Given that each has to shake hands with every other person, the graph has to be complete graph of ordet $8$ - $K_8$. We have to traverse $K_8$ such that the above conditions are satisfied.
I think that the condition (a) implies that no two hand shakes will happen simultaneously and this is what enables us decide to traverse the $K_8$.
But here traversing little different than Eulerian path or Hamiltonian. If I have vertices $a,b,c$ then I can go from $a$ to $b$. Now I have an option to go to $c$ from $a$ or $b$ because of condition (b). But I can not traverse back from $b$ to $a$ because traversing through an edge means a handshake, so if person has to have two consecutive handshake then I have to go to $b$ then Again jump to vertex $a$ and then go to $c$.
I am not able to proceed further. What can I do?