1
$\begingroup$

In the process of asking this question, I found that it has already been asked here. However I'm looking for critique of my proof and whether it can be extended.

Here's the problem paraphrased from the source:

Some out of $2n$ people at a party shook hands amongst themselves. But no group of $3$ people shook hands with each other. Show that the number of handshakes did not exceed $n^2$.

Proof: Consider an arbitrary graph $G$ over $2n$ vertices containing no triangles. Select a vertex $v$ such that it is adjacent to $(n+k)$ other vertices; for some $k, 0 \lt k \lt n$. If such a vertex does not exist then the proof follows.

Let the neighbours of $v$ be in set $K$, and all the other vertices of $G$(except $v$) be in $L$. There can be no edges amongst any of the $(n+k)$ vertices of $K$ as this would create a triangle with $v$. No vertex in $L$ can be connected to $v$ as well as to a vertex in $K$; since $\require{enclose} \enclose{horizontalstrike}{1\le(n+k)}$, we need not consider this case as this will give less than $n^2$ edges.

Thus, there may be edges between $K$ and $L$, and also amongst the vertices of $L$ themselves. At best, each vertex in $L$ is connected to each vertex in $K$- this gives $(n+k)(n-k-1)$ edges between the two sets.

Let $u_1$ and $u_2$ be two vertices in $L$. If $(u_1, u_2)$ is an edge, then there are at most $(n+k)$ edges between $K$ and $\{u_1, u_2\}$(in addition to the edge $(u_1, u_2)$), which is certainly less than the $2(n+k)$ obtainable by not having $(u_1,u_2)$ as an edge. Thus, it is optimal for no two vertices in $L$ to be adjacent.

In conclusion, there are at most $(n+k)+(n+k)(n-k-1) = n^2 - k^2 \le n^2$ edges in G. $\blacksquare$


Kindly point out loopholes in the proof.

Also, can the above argument be extended to show that an order $2n$ graph with $n^2$ edges and no triangles is bipartite?(where $K$ and $L\cup\{v\}$ is a partition.)

Edit: For anyone looking for more information, this is Mantel's Theorem.

$\endgroup$
  • 1
    $\begingroup$ "No vertex in $L$ can be connected to $v$ as well as to a vertex in $K$" - already by definition of $L$, the vertices in $L$ are not connected to $v$. $\endgroup$ – Hagen von Eitzen May 24 '17 at 16:57
  • $\begingroup$ Loophole: It is not immediately clear that you can consider the (possible) edges from $K$ to $u_1, u_2$ independently from edges from $K$ to other points in $L$. I.e., your "optimization" for $u_1,u_2$ might break something elsewhere $\endgroup$ – Hagen von Eitzen May 24 '17 at 17:02
  • $\begingroup$ Since edges from $K$ only go to $L$, we count over all vertices in $L$ only. That way also avoids double counting. Also, $u_1, u_2$ is an arbitrary pair so it alright, isn't it? $\endgroup$ – Akay May 24 '17 at 17:08

Your Answer

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

Browse other questions tagged or ask your own question.