Edge Counts in Complete Multipartite Graphs

Counting Edges Across the Parts

In an extremal graph problem, a construction is useful only if its size can be counted precisely. Complete multipartite graphs make that count depend directly on the sizes of their vertex parts: edges occur between different parts, and never within a part. The main task is therefore to count pairs of vertices that lie in different parts, without counting any edge twice.

Throughout, graphs are finite and simple. A simple graph has no loops or multiple edges. Let $k$ be a positive integer, and let $V_1,\ldots,V_k$ be pairwise disjoint vertex sets whose union is $V$. Write $n_i=|V_i|$ and $n=|V|=\sum_{i=1}^k n_i$. We allow a part to be empty; in the usual examples all parts are nonempty.

Definition: The complete multipartite graph with parts $V_1,\ldots,V_k$ has vertex set $V$, and two distinct vertices are adjacent exactly when they lie in different parts. It is denoted $K_{n_1,\ldots,n_k}$. Thus its edge set is the union, over all $1\le i<j\le k$, of the pairs $uv$ with $u\in V_i$ and $v\in V_j$.

Each $V_i$ is an independent set: no two vertices in the same part are adjacent. Every possible edge between two different parts is present. In particular, “complete” describes all cross-part edges being present, not edges within a part.

The Edge-Count Formula

Theorem: If $G=K_{n_1,\ldots,n_k}$, where the part sizes are nonnegative integers, then $$|E(G)|=\sum_{1\le i<j\le k}n_i n_j =\frac{n^2-\sum_{i=1}^k n_i^2}{2},\qquad n=\sum_{i=1}^k n_i.$$

Proof. Fix two different parts $V_i$ and $V_j$, with $i<j$. Every vertex of $V_i$ is adjacent to every vertex of $V_j$, so the edges between these parts correspond to choosing one vertex from each. There are $n_i n_j$ such choices and hence $n_i n_j$ such edges. Every edge has endpoints in exactly one pair of different parts, so the sets of edges counted for different pairs of parts are disjoint. Summing gives $|E(G)|=\sum_{i<j}n_i n_j$, including when some part is empty, since then the corresponding product is zero.

For the second expression, expand the square of the sum of the part sizes: $$n^2=\left(\sum_{i=1}^k n_i\right)^2 =\sum_{i=1}^k n_i^2+2\sum_{1\le i<j\le k}n_i n_j.$$ Subtract $\sum_i n_i^2$ from both sides and divide by $2$. The result is $2\sum_{i<j}n_i n_j=n^2-\sum_i n_i^2$, which gives the stated formula. These counts also cover $k=1$: the sum over pairs of parts is empty, and the displayed difference is $(n_1^2-n_1^2)/2=0$, as there are no edges within the sole part. $\square$

The first expression counts edges by the pair of parts they join. The second starts with all vertex pairs and removes the pairs lying inside parts. In fact, the number of all unordered pairs of distinct vertices is $\binom n2$, and the number of pairs inside part $V_i$ is $\binom{n_i}{2}$. Their difference is another useful form of the same count:

|E(G)|=\binom n2-\sum_{i=1}^k\binom{n_i}{2}.

This last identity follows because every pair of distinct vertices either lies in one part or in two different parts, and the two possibilities do not overlap. It gives an independent way to check calculations. It is also important to use unordered pairs: an edge $uv$ is the same edge as $vu$, not two edges.

Worked Counts

Worked Example: Two Parts

Let $V_1=\{a,b,c\}$ and $V_2=\{d,e,f,g\}$. Define $G$ to have vertex set $V_1\cup V_2$ and edge set consisting of every pair $uv$ with $u\in V_1$ and $v\in V_2$, and no other edges. Thus $G=K_{3,4}$.

There is just one pair of parts, so the cross-part count is $3\cdot4=12$ edges. To check by listing the edges, the vertices $a,b,c$ each join to $d,e,f,g$. The three groups $ad,ae,af,ag$; $bd,be,bf,bg$; and $cd,ce,cf,cg$ contain $4+4+4=12$ distinct edges.

A second check uses all pairs minus pairs within parts. There are $7=3+4$ vertices, giving $\binom72=7\cdot6/2=21$ total pairs. The within-part counts are $\binom32=3$ and $\binom42=4\cdot3/2=6$. Therefore the number of cross-part pairs is $21-3-6=12$, agreeing with the first count.

Check: A vertex in $V_1$ has its four neighbors in $V_2$; a vertex in $V_2$ has its three neighbors in $V_1$. The degree sum is $3\cdot4+4\cdot3=12+12=24$, which counts every edge twice and gives $24/2=12$ edges.

Worked Example: Three Parts

Take $V_1=\{a,b\}$, $V_2=\{c,d,e\}$, and $V_3=\{f\}$. Define $G$ to have vertex set $V_1\cup V_2\cup V_3$, with every pair from different parts as an edge and no pair from the same part as an edge. This is $K_{2,3,1}$.

Count one pair of parts at a time. Between $V_1$ and $V_2$ there are $2\cdot3=6$ edges: $ac,ad,ae,bc,bd,be$. Between $V_1$ and $V_3$ there are $2\cdot1=2$ edges: $af,bf$. Between $V_2$ and $V_3$ there are $3\cdot1=3$ edges: $cf,df,ef$. The edge set is exactly the union of these three lists, so the total is $6+2+3=11$.

Check by subtracting within-part pairs from all pairs. The graph has $2+3+1=6$ vertices, so there are $6\cdot5/2=15$ total pairs. The within-part counts are $2\cdot1/2=1$, $3\cdot2/2=3$, and $1\cdot0/2=0$. Thus $15-1-3-0=11$ cross-part pairs.

Check: The degrees in $V_1$ are both $3+1=4$; in $V_2$ they are all $2+1=3$; and the degree of $f$ is $2+3=5$. Their sum is $2\cdot4+3\cdot3+1\cdot5=8+9+5=22$, so the edge count is $22/2=11$.

Worked Example: Four Parts

Let $V_1=\{a\}$, $V_2=\{b,c\}$, $V_3=\{d,e\}$, and $V_4=\{f,g,h\}$. Define $G$ on the union of these four sets, with an edge between every pair in different parts and no edge between vertices in the same part. Thus $G=K_{1,2,2,3}$.

There are six pairs of parts. Their edge counts are $1\cdot2=2$ between $V_1,V_2$; $1\cdot2=2$ between $V_1,V_3$; $1\cdot3=3$ between $V_1,V_4$; $2\cdot2=4$ between $V_2,V_3$; $2\cdot3=6$ between $V_2,V_4$; and $2\cdot3=6$ between $V_3,V_4$. Each edge belongs to exactly one of those six groups. Adding them gives $2+2+3+4+6+6=23$ edges.

The independent all-pairs check has $1+2+2+3=8$ vertices, so there are $8\cdot7/2=28$ pairs. The numbers of pairs inside the four parts are $1\cdot0/2=0$, $2\cdot1/2=1$, $2\cdot1/2=1$, and $3\cdot2/2=3$. Hence $28-0-1-1-3=23$ pairs join different parts.

Check: A vertex in $V_1$ has degree $2+2+3=7$. Each vertex in $V_2$ or $V_3$ has degree $1+2+3=6$. Each vertex in $V_4$ has degree $1+2+2=5$. The total degree is $1\cdot7+2\cdot6+2\cdot6+3\cdot5=7+12+12+15=46$, and $46/2=23$ edges, as found by both pair counts.

Degrees and Useful Checks

Proposition: In $K_{n_1,\ldots,n_k}$, every vertex in part $V_i$ has degree $n-n_i$.

Proof. Fix a vertex $v\in V_i$. By the definition of a complete multipartite graph, $v$ is adjacent to every vertex outside $V_i$ and to no vertex inside $V_i$. There are $n-n_i$ vertices outside $V_i$. Therefore $\deg(v)=n-n_i$. If $V_i$ is empty, there is no vertex in that part to check; for every nonempty part the formula applies to each of its vertices. $\square$

This proposition gives a further check on the edge formula. Summing degrees part by part gives $\sum_{i=1}^k n_i(n-n_i)$. Each edge contributes one to the degree of each of its two endpoints, so this sum is twice the number of edges. Algebraically, the degree sum is $n\sum_i n_i-\sum_i n_i^2=n^2-\sum_i n_i^2$, using $\sum_i n_i=n$. Dividing by $2$ recovers the theorem’s formula.

The count depends only on the part sizes, not on the names of the vertices. It can therefore be useful to check a proposed count in two different ways: add the products $n_i n_j$ over pairs of parts, or compute $\binom n2-\sum_i\binom{n_i}{2}$. A disagreement indicates an arithmetic or counting error.

Common Counting Pitfalls

Mistake: treating each part as if it connected to itself. For $K_{3,4}$, a wrong calculation might use $3\cdot3+4\cdot4=9+16=25$, on the mistaken assumption that each part contributes its own edges. But those products count ordered choices within parts, not edges of $K_{3,4}$; the graph has no within-part edges. The correction is to count across the two parts: $3\cdot4=12$.

Mistake: counting each edge twice. A vertex in $V_i$ has $n-n_i$ neighbors, but summing those degrees counts every edge at both endpoints. Thus the degree sum must be divided by $2$. For the four-part example, the degree sum is $46$, not $46$ edges: the correct edge count is $46/2=23$.

Mistake: subtracting the wrong pairs. The expression $\binom n2$ counts all unordered pairs, including those within the parts. To count only edges, subtract $\binom{n_i}{2}$ for every part. The within-part counts must use combinations, not $n_i^2$, because a pair of vertices is unordered and a vertex cannot form an edge with itself.

These formulas provide the counting step for explicit multipartite constructions. They do not, by themselves, determine which part sizes should be chosen in a particular extremal problem; that question requires a separate argument.

Check Your Understanding

For each question, state the part sizes and show enough arithmetic to verify the count.

How many edges does $K_{2,5}$ have? Check by counting all vertex pairs and subtracting within-part pairs.
For $K_{1,2,4}$, compute the edge count by summing over pairs of parts, then check it using the degree sum.
Explain why $\sum_i n_i^2$ is not the number of edges within the parts, and give the correct within-part count.
Prove directly from the definition that an empty part contributes zero to the pair-of-parts formula.
For a vertex in a part of size $n_i$, explain why its degree is $n-n_i$, rather than $n-1$.