2
$\begingroup$

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

My solution

n Let G be a graph with 4 vertices, one vertex representing each person in the group. Join two vertices u and v by an edge if and only if u and v are friends. Then the degree of each vertex equals the number of friends that the corresponding person has. If each person has exactly 3 friends, then each vertex has degree 3. Therefore, the total degree would be 3 · 4 = 12. This is an even number.

$n\equiv 0\pmod{2}$ and $n>3$

So It is possible.

Is this correct?

$\endgroup$
3
  • 16
    $\begingroup$ Suppose that they are all friends. Then they all have exactly 3 friends. $\endgroup$ Nov 11, 2015 at 18:52
  • $\begingroup$ Can you be friends with yourself? $\endgroup$ Nov 11, 2015 at 19:08
  • $\begingroup$ @MarsOneRover No $\endgroup$
    – Micky
    Nov 11, 2015 at 19:09

3 Answers 3

7
$\begingroup$

Easy solution. They're all friends with each other but not themselves. That's all, no graphs.

$\endgroup$
1
$\begingroup$

Your graph model (people are vertices and edges denote friendship) is a reasonable one. The question then boils down to "Does there exists a graph on four vertices in which every vertex is of degree three?".

The problem with your current solution is you do not demonstrate that such a graph exists. The sum of degrees of any graph is even, so this says nothing about the existence of the graph we're interested in.

There are two main ways to treat such questions in general: Havel-Hakimi and Erdos-Gallai. Both theorems given necessary and sufficient conditions for the existence of graphs with vertices of specified degrees.

That is all overkill for this question, however. Start with four vertcies and start adding in edges as necessary. You will quickly realize that the complete graph on four vertices satisfies your constraints.

$\endgroup$
0
$\begingroup$

The complete graph on $4$ vertices, $K4$, has degree sequence $d(k4) = \{3,3,3,3\}$

So yes, it is possible.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .