Maximum Number of Edges in a Graph Without a Cycle of length $4$

Solution 1:

This is a partial case of a well-known question (see, for instance, this: what is the maximum number $E(n)$ of edges an $n$-vertex graph can have so that the resulting graph contains no 4-cycle?

Referenced there Füredi’s paper deals with large $n$, but the proof of the upper bound for $E(n)$ is much more simple. For instance, I copy here a fragment of my paper “On graphs without 4-cycles” from 2001 in which I reproved Reiman’s result from 1958. :-)

Let $G$ be an $n$-vertex graph and $M_G$ be the adjacency matrix of the graph $G$. Then the graph $G$ contains no 4-cycles iff the matrix $M_G$ contains no rectangles with unit vertices.

Proposition 1. $E(n)\le\frac{n+n\sqrt{4n-3}}4$.

Proof Let $G$ be an $n$-vertex graph without $4$-cycles. Let $l_i$ be the number of units in the $i$-th row of the matrix $M_G$. There are $\binom n2$ possible pairs of columns of the matrix $M_G$. We say that a row $i$ forbids a pair of columns $\{j,k\}$ iff $m_{ij}=m_{ik}=1$. Then the $i$-th row forbids $\binom {l_i}2$ pairs and therefore $\sum\binom {l_i}2\le \binom n2$. Let $2E=\sum l_i$. Using the inequality between an arithmetic mean and a quadratic mean we obtain $4E^2-2nE\le n^2(n-1)$ which implies $E\le\frac{n(\sqrt{4n-3}+1)}4$.$\square$

In particular, $E(10)\le 17$. But we can refine this bound using the fact that when the sum of $l_i$’s is fixed the minimum of $\sum {l_i \choose 2}$ is attained when $l_i$’s differs by at most $1$. So if $\sum l_i=34$ then the minimum of $\sum {l_i \choose 2}$ is attained when four of $l_i$’s equal $4$ and six of $l_i$’s equal $3$. Then $\sum {l_i \choose 2}=4\cdot {4 \choose 2}+6\cdot {3 \choose 2}=54>45={n \choose 2}$, a contradiction. Thus $E(10)\le 16$. The following Joseph DeVincentis’ example from Erich Friedman’s page shows that this bound is exact.

Solution 2:

Alex Ravsky's answer shows that a $C_4$-free simple graph on $10$ vertices has at most $16$ edges. Here is a simple proof of the OP's easier task of showing that it has at must $27$ edges.

Call the vertices $v_i\ (i=1,\dots,10)$ and let $d_i=|N(v_i)|$ be the degree of the vertex $v_i.$

Now $$d_i+d_j=|N(v_i)|+|N(v_j)|=|N(v_i)\cup N(v_j)|+|N(v_i)\cap N(v_j)|\le10+|N(v_i)\cap N(v_j)|.$$ Assuming $i\ne j,$ we have $|N(v_i)\cap N(v_j)|\le1$ (since there is no $C_4$), and so $d_i+d_j\le11.$
It follows that $$\sum_{i=1}^{10}d_i=(d_1+d_2)+(d_3+d_4)+(d_5+d_6)+(d_7+d_8)+(d_9+d_{10})\le5\cdot11=55$$ whence the number of edges is at most $\left\lfloor\frac{55}2\right\rfloor=27.$