Basic graph theory
Level
pending
Prior to a committee’s reunion, some of its ten members shook hands. Is it possible that the number of handshakes have been, in some order equal to 1,1,1,3,3,3,4,6,7,8.
No
Yes
Sometimes
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Look at the committee’s members as the vertices of a graph , with two vertices being adjacent if the corresponding people shook hands. Then, if the situation just described could have occurred, the degrees of the vertices of the graph would have been, in some order, equal to 1, 1, 1, 3, 3, 3, 4, 6, 7 and 8. But since we would have an odd number of vertices of odd degree, , such a situation cannot have occurred.