By counting by 2 ways, show a cycle of four acquaintances exists In a conference there were $35$ participants. There are $110$ couples who know each other. Prove that it is possible to choose 4 members to sit at a round table such that two people sitting close together know each other.
This is the last problem in a workbook "Solving combinatorial math by 'counting in two ways' " by Nguyen Tang Vu (original here in Vietnamese, Problem 10 on page 62) "published in the math journal Star Education." I find it quite interesting because it can't be solved in the usual ways.
Here's all I did:
Suppose any $2$ people can't get along with $2$ other people.
Count the number $S$ of triples of the form $(A,B,C)$ where person $A$ and person $B$ are familiar with person $C$.
Method 1: Count by $A, B$. We have $S \le \binom{35}{2}$ (according to the assumption)
Method 2: Count by $C$:
Let $a_i$ be the number of people who know the $i$-th person. We have:
$$ a_1 + a_2 + ... + a_{35} = 220 $$
So $\binom{a_1}{2} + \binom{a_2}{2} + \binom{a_3}{2} + \ldots + \binom{a_{35}}{2} \ge 585$.
I want to prove what I assume is wrong, but $\binom{35}{2} = 595$ is still greater than $585$. I tried to tighten my inequality but I can't. Can anyone give me a hint, please?
 A: The immediate difficulty can be explained as a mistake in the problem statement.  The author wrote me (via Facebook Messenger), "it's my mistake, exactly is $111$ pairs," rather than the $110$ couples noted in the Question.
The general problem:

For $n$ conference participants, how many couples $f(n)$ could be known to each other without including a "cycle" of four who could be seated with each between two of their acquaintances?

is actively studied in the combinatorial research literature, e.g. Extremal Graphs Without 4-Cycles.  Readers should not be put off by the vocabulary of graph theory to discuss these problems.  The participants form the vertices of a graph whose edges are the pairs of people who know one another.
Assume for a graph with $n = 35$ vertices that there are no $4$-cycles. Then any two vertices $A,B$ will have at most one adjacent vertex in common; if they share two distinct "neighbors" $C,D$, altogether they would form a $4$-cycle subgraph (which we assume does not exist):
$\require{AMScd}$
$$ \begin{CD}
A @>>> C\\
@AAA @VVV\\
D @<<< B
\end{CD} $$
So the count $S$ of all undirected paths of length two, like $A\frac{\phantom{XXX  }}{\phantom{XXX}}C\frac{\phantom{XXX}}{\phantom{XXX}}B$ , is bounded above by the count of unordered pairs $\{A,B\}$ of vertices, $\binom{35}{2}$. Thus $S\le 595$.
We have the second way to count $S$.  Consider for each vertex $C$ how many distinct pairs of neighbors $A,B$ it has that form a path of length two, $A \frac{\phantom{XXX  }}{\phantom{XXX}} C \frac{\phantom{XXX}}{\phantom{XXX}} B$.  Thus, using the Question's notation $a_i$ for the numbers of neighbors at each vertex:
$$ S = \sum_{i=1}^{35} \binom{a_i}{2} $$
We don't know exactly what all the vertex degrees $a_i$ are, so we can't directly evaluate $S$ from the above. But we do know by the Handshaking Lemma that the sum of all the $a_i$'s is twice the number of edges.
If there are $111$ edges, $S$ must be at least the minimum of the expression above where $\sum a_i = 222$.  The minimum would be attained by spreading the degrees as equally as possible among the $35$ vertices, namely twelve vertices of degree $\lceil 222/35 \rceil = 7$ and the other $23$ vertices of degree $\lfloor 222/35 \rfloor = 6$.  So $S \ge 12\binom{7}{2} + 23\binom{6}{2} = 597$.
Since that contradicts the previous upper bound on $S$, we know that $111$ edges on $35$ vertices guarantees a $4$-cycle subgraph, which is what the (corrected) problem calls for.  However it leaves the interesting problem as originally stated (with $110$ edges) unsolved; can a $4$-cycle be avoided with only $110$ edges?  I did not find a definitive answer in researching this Question.
