Maximize edges under clique restrictions

Try

How many edges can a graph have without containing a triangle? A complete bipartite graph has no triangle, and balancing its two parts gives floor (n²/4) edges. Mantel’s theorem proves that no triangle-free graph can do better. The result is an extremal statement: it optimizes a quantity under a forbidden-structure condition, rather than asking whether one specific graph contains a triangle.

Predict

Predict why a local degree restriction can bound the global edge count. If uv is an edge in a triangle-free graph, the neighborhoods of u and v are disjoint; a common neighbor would complete a triangle. Hence d(u)+d(v)≤n. Summing this inequality over all edges counts each vertex degree once for each incident edge, producing Σd(v)²≤nm. Cauchy–Schwarz supplies the complementary lower bound on that sum.

Experiment

Compare balanced bipartite constructions.

Vertices n	Part sizes	Edges
5	2, 3	6
6	3, 3	9
7	3, 4	12

For m edges, Cauchy gives Σd²≥(Σd)²/n=4m²/n. Combine with Σd²≤nm and cancel m when positive to obtain m≤n²/4. The empty graph case is immediate.

Understand

Turán’s theorem generalizes this: among K_(r+1)-free graphs on n vertices, a complete r-partite graph with parts as equal as possible has the maximum number of edges. Here is the symmetrization mechanism for r≥1. Choose an edge-maximizing forbidden-clique-free graph, and among those maximize Σd². If two nonadjacent vertices have different degrees, replace the lower-degree vertex by a twin of the higher-degree one, increasing edges without creating a forbidden clique. Therefore nonadjacent vertices have equal degrees. If their neighborhoods differ, consider cloning either one to the other. Edge count remains fixed. For vertices in the symmetric difference of the neighborhoods, the two possible degree-square changes sum to a positive amount, namely two per affected vertex. Thus one cloning increases Σd², contradiction.

Apply

Consequently any two nonadjacent vertices have identical neighborhoods. Nonadjacency, together with equality, partitions vertices into independent twin classes, and every pair in different classes is adjacent. The graph is complete multipartite. It has at most r nonempty parts, since choosing one vertex from each part forms a clique. For fixed part sizes n_i, its edge count is (n²−Σn_i²)/2. Moving a vertex from a part at least two larger than another increases this count. Splitting a nontrivial part also increases edges when fewer than min (r, n) parts are present. Hence the optimum is the balanced r-partite construction, allowing empty parts when r>n. This proves the extremal value without claiming a full classification of every equality case from the tie-breaking choice alone.

Continue

For n=8 and r=3, parts 3, 3, 2 give 21 edges and exclude K4. A graph with 22 edges must therefore contain K4, but a graph with fewer edges may still contain one. Record the direction of implication carefully. The proof uses finite simple undirected graphs; multiple edges would make the edge optimization unbounded without additional restrictions. Extremal arguments often pair an explicit construction with an upper bound, and both halves are needed before calling a candidate optimal.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with force structure in every coloring.