Graph Theory Question

Question

This is a two part question.

In a reunion of 20 people, there are 48 pairs of people that know each other.

a) Justify why there is, at least, one person who knows, at most, other 4 persons.

b) Suppose there is a single person who knows at most other 4 persons. How many people does that person knows exactly?

I'm unsure about my answers:

a) I suppose there a vertex with degree 4 and 19 with degree 5.

19*5 + 4 = 99

and, as the summation of the degrees of the vertexes should give 2*E, with E being the number of edges,

and

99 > 96 = 2*E

I conclude this is not possible.

b) I think this problem is poorly stated. If there is a single person that knows "at most" 4 other persons, then that person can know 4, 3, 2 or 1 persons. I can't know exactly.

Answer 1

20 verts, 48 edges. V = 20, E = 48.

a) Proposition: There is no person who knows at most 4 other persons. Equivalent is: All persons do not know at most 4 other persons. That is, all persons know at least 5 others. Then the total degree must be 5V = 100. But there are only E = 48 edges, so the total degree is 2E = 96. This is a contradiction, so the proposition is false. Therefore there is at least one person who knows at most 4 others.

b) Given: There is exactly one person who knows at most 4 others. Then all other persons must know at least 5 others. This gives a total degree of at least 5(V-1) = 95 for those 19 persons. The total degree is 2E = 96, so the single remaining person necessarily has degree 96 - 95 = 1. So he knows exactly one other person.

Answer 2

Question a)

Your approach is generally right, but two problems:

1. That's an invalid supposition: no such graph can exist. (sum of degrees is odd!)
2. You need to explicitly justify that it can't help to increase the degree of some vertex.

You're better off looking at an arbitrary 20 vertex graph where each vertex has degree at least 5, and arguing that would result in too many edges. That argument would apply to all graphs.

Question b)

Try it. The constraint that 19 vertices are degree at least 5 uses up most of the edges.

Answer 3

For part b: Isn't it either 0 or 1? The other 19 people all know at least 5 people, that's a given. So if we start by constructing a graph where 18 people have degree 5 and I person degree 4 (and loser-guy degree 0), we have total edges: 18*5+4 = 94, with 1 more edge to place. Can't we choose to place that edge either between 4-friend guy and loser guy, or 4-friend guy and someone else?

In other words, we either wind up with a graph of: a) 1 vertex of degree 6, 18 of degree 5, 1 of degree 0 or b) 19 of degree 5, 1 of degree 1