Graphs with degree sets of maximal cardinality: a handshaking problem revisited

Abstract

At a party attended by p people, some handshaking took place. No one shook hands with himself/herself nor with the same person more than once. After all the handshaking was completed, one member of the group asked each of the others how many times he/she had shaken hands and received a different answer from each. How many hands did the questioner shake? This handshaking problem lends itself nicely to the use of graphs as models, and its solution appeared in an earlier issue of this journal. The note summarizes the relevant results thus far and extends the work to include a recursive algorithm that generates the appropriate graphs of order p with degree sets of maximal cardinality.