Balancing Parts in Turán Graphs

Why Part Sizes Should Be Balanced

A complete multipartite graph has all possible edges between different parts and no edges within a part. If the number of vertices is fixed, concentrating many vertices in one part removes many potential edges: pairs within that part are not adjacent. The key question is how to distribute the vertices among a fixed number of parts to maximize the edge count. A local calculation answers it: moving a vertex from a part that is at least two larger than another part strictly increases the number of edges.

Throughout, \(n\) is a nonnegative integer and \(r\) is a positive integer. We allow empty parts, so the \(r\) parts are labeled sets that partition the vertex set; some of these sets may be empty. Graphs are finite and simple.

Definition: A complete \(r\)-partite graph is a graph whose vertex set is partitioned into \(r\) parts \(V_1,\dots,V_r\), with an edge between every pair of vertices in different parts and no edge between vertices in the same part. Write \(a_i=|V_i|\) for the size of part \(i\). The parts are balanced if \(|a_i-a_j|\le 1\) for every pair \(i,j\).

For given part sizes, the edge count is the sum of the products of the sizes of every pair of parts: each such product counts the edges between those two parts. Equivalently, among the \(\binom n2\) pairs of vertices, the only nonedges are pairs that lie within a part. Thus

|E|=\sum_{1\le i<j\le r}a_i a_j =\binom{n}{2}-\sum_{i=1}^r\binom{a_i}{2} =\frac{1}{2}\left(n^2-\sum_{i=1}^r a_i^2\right).

These counts also apply when some \(a_i=0\): an empty part contributes no vertices and no edges. The formula makes the balancing question an optimization of the sum of the squared part sizes. We will establish the required optimization directly by counting the effect of a single vertex transfer.

The Edge-Transfer Calculation

Lemma: Suppose two parts have sizes \(a\) and \(b\), where \(a\ge b+2\). Moving one vertex from the part of size \(a\) to the part of size \(b\) increases the edge count by exactly \(a-b-1\).

Proof. Let the two parts be \(A\) and \(B\), with \(|A|=a\) and \(|B|=b\), and choose a vertex \(x\in A\). Before the move, the edges between \(A\) and \(B\) number \(ab\). Afterwards, the two sizes are \(a-1\) and \(b+1\), so the edges between those parts number \((a-1)(b+1)\). Every other part contributes the same number of edges as before: \(x\) remains in a part different from each of them, and all other vertices remain where they were. Therefore the change in the total edge count is \[ (a-1)(b+1)-ab =ab+a-b-1-ab =a-b-1. \] Since \(a\ge b+2\), we have \(a-b-1\ge1\), so the change is strictly positive. \(\square\)

The size condition matters. If \(a=b+1\), the change is zero: transferring a vertex merely exchanges the two part sizes. If the sizes are equal, transferring a vertex from one to the other decreases the edge count by one. Only a difference of at least two guarantees a strict improvement in the direction of the smaller part.

Balanced Parts Give the Maximum

Theorem: Among complete \(r\)-partite graphs on \(n\) vertices, the edge count is maximum exactly when the part sizes are balanced. In particular, all balanced choices of part sizes give the same maximum edge count.

Proof. There are finitely many ways to distribute \(n\) vertices among \(r\) labeled parts, so a maximum edge count exists. Suppose a complete \(r\)-partite graph attaining this maximum has two part sizes \(a\) and \(b\) with \(a\ge b+2\). By the Lemma, transferring one vertex from the larger part to the smaller part increases the edge count by \(a-b-1\ge1\). This contradicts maximality. Therefore every maximizing graph has balanced part sizes.

It remains to show that every balanced choice has the same edge count and is maximizing. By integer division, there are unique integers \(q,s\) such that \(n=qr+s\) and \(0\le s<r\). In any balanced list of \(r\) nonnegative integer part sizes with sum \(n\), each size is either \(q\) or \(q+1\). To see this, let the smallest size be \(k\). Every size is \(k\) or \(k+1\), so their sum is at most \(r(k+1)\) and at least \(rk\); the number of sizes equal to \(k+1\) is therefore the remainder when the sum is divided by \(r\). Hence the balanced list must consist of \(r-s\) parts of size \(q\) and \(s\) parts of size \(q+1\). All balanced lists have the same sizes up to their order, and thus the same edge count by the edge-count formula. A maximum exists and, as proved above, must be balanced. Since every balanced choice has that same edge count, every balanced choice is also maximizing. \(\square\)

This proof covers the boundary cases as well. If \(n=0\), then \(q=s=0\), every part is empty, and the graph has no edges. If \(r>n\), then \(q=0\) and \(s=n\), so a balanced list has \(n\) singleton parts and \(r-n\) empty parts. Vertices in distinct singleton parts are adjacent to one another.

Worked Edge Transfers

Worked Example: Improving Part Sizes \(5,3,2\)

Let \(V=\{1,2,\dots,10\}\), with parts \(V_1=\{1,2,3,4,5\}\), \(V_2=\{6,7,8\}\), and \(V_3=\{9,10\}\). Define \(G=(V,E)\) by \(E=\{uv:u\in V_i,\ v\in V_j,\ i\ne j\}\); thus every pair in different listed parts is an edge and no pair within a listed part is an edge.

The edge count is the sum of the products for pairs of parts: \[ |E(G)|=5\cdot3+5\cdot2+3\cdot2=15+10+6=31. \] The largest part has size \(5\) and the smallest has size \(2\), so transfer vertex \(5\) from the first part to the third. The new parts are \(\{1,2,3,4\}\), \(\{6,7,8\}\), and \(\{5,9,10\}\), of sizes \(4,3,3\). The edge-transfer calculation gives an increase of \(5-2-1=2\). The new edge count is \(4\cdot3+4\cdot3+3\cdot3=12+12+9=33\).

Check: Using the alternative formula, the original count is \(\frac12(10^2-(5^2+3^2+2^2))=\frac12(100-38)=31\). After the transfer it is \(\frac12(100-(4^2+3^2+3^2))=\frac12(100-34)=33\), confirming the increase of \(2\).

Worked Example: Repeated Transfers Toward Balance

Let \(V=\{1,2,\dots,7\}\), with parts \(V_1=\{1,2,3,4\}\), \(V_2=\{5\}\), \(V_3=\{6\}\), and \(V_4=\{7\}\). Define \(E=\{uv:u\in V_i,\ v\in V_j,\ i\ne j\}\). The part sizes are \(4,1,1,1\), and the edge count is \(4\cdot1+4\cdot1+4\cdot1+1\cdot1+1\cdot1+1\cdot1=15\).

Transfer one vertex from the part of size \(4\) to a part of size \(1\). The sizes become \(3,2,1,1\), and the increase is \(4-1-1=2\). Transfer one vertex from the part of size \(3\) to a part of size \(1\). The sizes become \(2,2,2,1\), and this increase is \(3-1-1=1\). The resulting sizes differ by at most one, so they are balanced.

Check: For sizes \(2,2,2,1\), the pairwise products sum to \(2\cdot2+2\cdot2+2\cdot1+2\cdot2+2\cdot1+2\cdot1=4+4+2+4+2+2=18\). Independently, \(\frac12(7^2-(2^2+2^2+2^2+1^2))=\frac12(49-13)=18\). The total increase is \(18-15=3\), equal to the two transfer gains \(2+1=3\).

Worked Example: More Parts Than Vertices

Let \(V=\{1,2,3,4\}\) and use \(r=6\) parts: \(V_1=\{1\}\), \(V_2=\{2\}\), \(V_3=\{3\}\), \(V_4=\{4\}\), and \(V_5=V_6=\varnothing\). Define \(E=\{uv:u\in V_i,\ v\in V_j,\ i\ne j\}\). Every two distinct vertices belong to different singleton parts, so every pair is an edge: this graph is \(K_4\).

Its edge count is \(\binom42=4\cdot3/2=6\). The part sizes are \(1,1,1,1,0,0\), which differ by at most one. For comparison, a distribution with sizes \(2,1,1,0,0,0\) has \(2\cdot1+2\cdot1+1\cdot1=5\) edges. Moving one vertex from the part of size \(2\) to an empty part increases the count by \(2-0-1=1\), giving the balanced sizes \(1,1,1,1,0,0\).

Check: The balanced graph has \(\binom42=4\cdot3/2=6\) edges, and the direct part-product count is \(1\cdot1+1\cdot1+1\cdot1+1\cdot1+1\cdot1+1\cdot1=6\). Thus the count agrees with \(K_4\), not with an edgeless graph.

Common Mistakes and a Useful Test

Overcounting the gain from a transfer. For part sizes \(5\) and \(2\), it is tempting to say that the transfer gains \(5-2=3\) edges. The exact comparison is between the old \(5\cdot2=10\) edges between these parts and the new \(4\cdot3=12\), so the gain is \(12-10=2\), not \(3\). The correct formula is \(a-b-1\): the moved vertex gains adjacency to the \(a-1\) vertices remaining in its original part, but it loses adjacency to the \(b\) vertices in its new part. In this case the difference is \((5-1)-2=2\).

Confusing balanced with equal. Equal part sizes are not always possible. For example, \(10\) vertices cannot be divided equally among \(3\) parts using integer sizes. The balanced sizes are \(4,3,3\), which differ by at most one. The theorem says these sizes maximize the edge count; it does not require every part to have the same size.

For a proposed complete multipartite graph, a practical check is to compare its largest and smallest part sizes. If their difference is at least two, one transfer from a largest part to a smallest part strictly increases the edge count. If every pair of sizes differs by at most one, the graph has the balanced size pattern established in the theorem.

Check Your Understanding

Use the edge-transfer formula and the edge-count expression to answer these questions.

For part sizes \(6,3,3\), calculate the increase from transferring one vertex from a largest part to a smallest part.
Explain why a transfer between parts of sizes \(4\) and \(3\) does not change the edge count.
List the balanced part sizes for \(n=11\) vertices and \(r=4\) parts.
For \(n=3\) and \(r=5\), describe the balanced part sizes and identify the resulting graph.
Why does the edge-transfer argument rule out an unbalanced graph as a maximizer?