I have a homework question in my discrete mathematics class as the title shows, I feel the answer is no, but googling this question seem's to contradict my answer. Let me explain:
So if they are asking about the number of people who do not know an odd number of people, they're asking about vertices with an even degree.
Theorem 1 in my book says:
In any graph, the sum of the degrees of all vertices is equal to twice
the number of edges.
which means the result of the left hand side equation above (DV = 2E) must be even. The graph of the problem could in terms of the theorem above could be represented as:
$2nv_1$ + $(2m+1)v_2$ = 2E
where $v_1$ is the amount of even numbered vertices, and $v_2$ is the amount of odd numbered vertices
In the case above , the value of $v_1$ is arbitrary in the scope of this question as any number multiplied against an even number is still even. What really matters is the amount of odd people no? Consider the graph
this is valid, and an odd number of even degrees correct? I'm so confused partly because of this answer I found online, which states that it shoulds be yes , when the above graph proves it can be no.
Am I just thinking of this problem wrong? Thanks for any explanation
Best Answer
Number of even degree vertices could be anything but the number of odd degree vertices must be an even number.