Problem:
dam, Benin, Chiang, Deshawn, Esther, and Fiona have internet accounts. Some, but not all, of them are internet friends with each other, and none of them has an internet friend outside this group. Each of them has the same number of internet friends. In how many different ways can this happen?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
This situation can be modeled with a graph having these six people as vertices, in which two vertices are joined by an edge if and only if the corresponding people are internet friends. Let be the number of friends each person has; then . If , then the graph consists of three edges sharing no endpoints. There are choices for Adam's friend and then ways to partition the remaining people into pairs of friends, for a total of possibilities. The case is complementary, with non-friendship playing the role of friendship, so there are possibilities in that case as well.
For , the graph must consist of cycles, and the only two choices are two triangles (-cycles) and a hexagon (-cycle). In the former case, there are ways to choose two friends for Adam and that choice uniquely determines the triangles. In the latter case, every permutation of the six vertices determines a hexagon, but each hexagon is counted times, because the hexagon can start at any vertex and be traversed in either direction. This gives hexagons, for a total of possibilities. The complementary case provides more. The total is therefore .
The problems on this page are the property of the MAA's American Mathematics Competitions