a In a group of 15 people is it possible for each person to

(a) In a group of 15 people, is it possible for each person to have exactly 3 friends? (b) In a group of 4 people, is it possible for each person to have exactly 3 friends? Why?

Solution

(a)

Here think 15 people as the 15 vertices of a graph G. Now join two vertices l and m by an edge if and only if people corresponding to vertices l and m are friends. Then in the resultant graph, the degree of each vertex equals the number of friends that the corresponding person has. Now suppose each person has exactly 3 friends, then in the graph each vertex has degree 3. Since there are total 15 vertices in the graph therefore, the total degree of the graph would be 3 · 15 = 45. This is an odd number, which is not possible because the total degree of a graph must be an even number. Hence, it is not possible that in a group of 15 people, each person to have exactly 3 friends.

--------------

(b)

Here think 4 people as the 4 vertices of a graph G. Now join two vertices l and m by an edge if and only if people corresponding to vertices l and m are friends. Then in the resultant graph, the degree of each vertex equals the number of friends that the corresponding person has. Now suppose each person has exactly 3 friends, then in the graph each vertex has degree 3. Since there are total 4 vertices in the graph therefore, the total degree of the graph would be 3 · 4 = 12. This is an even number, which is possible because the total degree of a graph must be an even number. Hence, it is possible that in a group of 4 people, each person to have exactly 3 friends.