edited by
998 views
2 votes
2 votes
In a party there are $2n$ participants, where $n$ is a positive integer. Some participants shake hands with other participants. It is known that there are no three participants who have shaken hands with each other. Prove that the total number of handshakes is not more than $n^2.$
edited by

3 Answers

5 votes
5 votes
If we divide whole 2n people into two equal size sets A and B. If two people allowed to handshake iff they belong to different sets.
If people represented as vertices (V) and each handshake is an edge between V1 and V2 then the maximum number of handshakes are nothing but the number of edges in a complete bipartite graph having two sets of vertices of size n each.

So, maximum number of handshakes = n*n

PS: I am using the fact that bipartite graph doesn't have any odd length cycle so it won't have any cycle of length 3.
0 votes
0 votes
[ Official answer by CMI]

Model this as a graph problem, we are looking for a graph without a triangle. We show that the maximum number of edges that a triangle-free graph on 2n vertices can have is n 2 . The proof by induction on n. The base cases n = 1, 2 are easy to see by inspection. For the inductive step, let n ≥ 3. If the graph G has no edges then there is nothing to prove. Otherwise, take an edge {x, y}, and consider the graph G0 on 2(n − 1) vertices obtained by deleting both the vertices {x, y} from G. By the inductive hypothesis, G0 has at most (n − 1)2 edges. Since graph G is trianglefree and {x, y} is an edge in G, there is no vertex v in G0 such that both {v, x} and {v, y} are edges in G. So the number of edges with one end-point in the set {x, y} and the other in the set of vertices of G0 is at most the number of vertices in G0 , namely 2(n − 1). Now the set of edges of G consists of (i) all the edges in G0 , plus (ii) the one edge {x, y}, plus (iii) the at most 2(n − 1) edges with exactly one end-point in {x, y}. So the number of edges of G is at most (n − 1)2 + 1 + 2(n − 1) ≤ n 2 .

Related questions

8 votes
8 votes
2 answers
3
Tesla! asked Feb 4, 2018
1,104 views
An FM radio channel has a repository of $10$ songs. Each day, the channel plays $3$ distinct songs that are chosen randomly from the repository.Mary decides to tune in to...