1
$\begingroup$

Consider an antireflexive, symmetric relation "is a friend of". Proof that in a group of $n$ people, there will always be an even number of people with an odd number of friends.

What I've already tried:

Suppose $A$ is the set of people with $|A| = n$. Consider the function $f: A \to \mathbb{N}_{<n}$ that maps a person to the number of friends he/she has ($<n$ because the relation we're looking at is antireflexive). The codomain of $f$ has exactly $n$ elements. $A$ and $\mathbb{N}_{<n}$ have the same number of elements and therefor we can always find a bijection, and thus a surjection, between the two sets. If $n$ is even, we can map all people to $n-1$, meaning everybody is everybody's friend. If $n$ is odd, we randomly take $(n-1)/2$ people and map them to $n-2$; the other half of the people can be mapped to $0$. This completes the proof.

I don't know if this is the correct way of proving these type of questions. Does anyone have other methods/ideas? Is my proof correct?

Thanks.

$\endgroup$
  • 3
    $\begingroup$ This is a graph theory problem. $\endgroup$ – Lord Shark the Unknown Jan 27 at 9:49
  • 2
    $\begingroup$ handshaking lemma is not it? $\endgroup$ – Bijayan Ray Jan 27 at 9:50
  • 2
    $\begingroup$ You seem to be deciding who should be friends with each other. You should accept that they have already decided who are friends already. $\endgroup$ – Lord Shark the Unknown Jan 27 at 9:51
1
$\begingroup$

Consider the $v_k$ denote a person observe that the total number of 'is friend of' is even because $v_x$ 'is friend of' $v_y$ implies the converse too. So now if number of people with odd number of friend is odd the "the total number of 'is friend of'" would be odd too hence contradiction which proves the assertion (you may also refer Wikipedia "handshaking lemma " for general graph theoretic proof)

$\endgroup$
0
$\begingroup$

Assume there are an odd number of people with an odd number of friends. Then the total number of friendship is $\frac{\text{odd*odd+even*even}}{2}$ which is not an integer. This is a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.