Winter Mathematical Competition

a) Let $G$ be a graph with the required property and minimum possible number of edges. If $G$ is not connected then adding a new edge which connects two components does not give a new 3-clique, a contradiction. Therefore $G$ is connected and it has at least $n-1$ edges. On the other hand, the graph $K_{1,n-1}$ has the required property. ($K_{m,n}$ is the graph with $m+n$ vertices which are divided into two sets of $m$ and $n$ elements, respectively, and two vertices are adjacent if and only if they belong to different sets; the edges are obviously $mn$.) Thus the answer is $n-1$.

b) Consider a graph with vertices $u_1,u_2,v_1,\dots ,v_{n-2}$ and edges all pairs $u_i{v}_j$, $i=1,2,j=1,\dots ,n-2$, together with $u_1{u}_2$. This graph has $n$ vertices, $2n-3$ edges and adding any new edge increases the number of the 4-cliques. Hence the required minimum number does not exceed $2n-3$. We shall prove by induction on $n$ that the minimum possible number of edges is $2n-3$ and it is attained only for a graph as above. The assertion is obvious for $n=4$. Assume that the assertion is proved for graphs with $n-1$ or less vertices. Let $G$ be a graph with the required property having $n\ge 5$, vertices and minimum possible number of edges.

Since adding of a new edge increases the number of the 4-cliques, the graph $G$ has four vertices $x_1,x_2,x_3,x_4$ which determine exactly five edges joining them. Next we assume that the missing edge is $x_1{x}_2$. Let $G^{\ast }$ be the graph which is obtained from $G$ by cluing the vertices $x_1$ and $x_2$ (i.e. we remove $x_1$ and $x_2$ from $G$, add a new vertex $u$ and save all remaining vertices; the new vertex is adjacent exactly to these vertices which were adjacent to at least one of $x_1$ and $x_2$, all old edges are saved). Then $$e(G^{\ast })\le e(G)-2\le 2n-5=2(n-1)-3.$$ Hence the graph $G^{\ast }$ has $n-1$ vertices, possesses the required property and has at most $2(n-1)-3$ edges. Then the induction hypothesis implies that $G^{\ast }$ has exactly $2n-5$ edges and it has the structure described above – two vertices of degree $n-2$ and all remaining of degree 2. At least one of the vertices of degree $n-2$ is $x_3$ or $x_4$, say $x_3$. Then the degree of $x_3$ in $G$ is $n-1$. Denote by $G^{\prime }$ the graph obtained from $G$ by removing the vertex $x_3$ and all edges from it. The graph $G^{\prime }$ has at most $n-2$ edges since $G$ has at most $2n-3$ edges. Moreover, $G^{\prime }$ has the property considered in a). Therefore it follows from the solution of a) that $G^{\prime }=K_{1,n-2}$. It is easy to see now that $G$ has the required structure and this completes the induction step.