Must the number of people...

979 Views Asked by At

Must the number of people at the party who do not know an odd number of people be even? Describe a graph model and then answers the question.

I'm confused because I do not understand the question. For example if we take people to be a vertex, then if there is an edge between them it means that people know each other, and the formula is $$\sum d(v) = 2*e$$ $\Rightarrow$ the sum of degrees of all vertices should be even so it means that there should be an even number of vertices. But why in the question is "people who do not know an odd number of other people be even"..?

2

There are 2 best solutions below

6
On

The number of people a person knows is the degree of a vertex. As you've noted, the sum of the degrees must be even. Thus the number of vertices of odd degree must be even. However, the question is asking about vertices of even degree, and there are no restrictions in this sense on these; all of the vertices in a cycle graph have even degree, and cycles can be of any length greater than $2$.

3
On

Construct a graph whose vertices are the people, and two vertices are adjacent if the two people know each other. The number of people who do not know an odd number of people is equal to the number of people who know an even number of people (because there are only two possibilities for the degree of a vertex - even or odd). So you are considering the number of vertices of even degree. This value is not restricted in any way. If the graph is an odd cycle, then the number of vertices of even degree is odd. So the answer to your question is a "no".