[ The Extreme Principle (Miscellaneous). ] [ Cauchy's Inequality $]$  [ Pairing and Grouping; Bijections ]

a) What is the maximum number of edges in a 30-vertex graph that contains no triangles?

b) What is the maximum number of edges in a 30-vertex graph that contains no complete subgraph of four vertices?
Select the vertex of the highest degree.

## Solution

a) Estimate. Let's choose a vertex $A$ of the highest degree $n$ and consider the subgraph $G$ formed by the vertices to which edges from $A$ lead. It is clear that there are no edges in this subgraph. Each vertex not in $G$ has a degree no greater than $n$, and the edges coming out of them are all the edges of the original graph. Thus, the total number of edges in the original graph does not exceed $n(30-n) \leq 15^{2}$.

Example. Divide 30 vertices into two groups of 15 and draw all edges connecting vertices from different groups. The resulting graph has no triangles and has 225 edges.

b) Estimate. Choose a vertex $A$ of the highest degree $n$ and consider the subgraph $G$ formed by the vertices to which edges from $A$ lead. It is clear that there are no triangles in this subgraph, so, as essentially proven in a), the number of its edges does not exceed $(n / 2)^{2}$. Thus, the total number of edges in the original graph does not exceed $(n / 2)^{2} + n(30-n) = 3 / 4 n(40-n) \leq 3 / 4 \cdot 20^{2} = 300$.

Example. Divide 30 vertices into three groups of 10 and draw all edges connecting vertices from different groups. The resulting graph has no complete 4-subgraphs and has 300 edges.

## Answer

a) 225 ; b) 300 edges.