Why the Part Sizes Determine the Parameters
A complete bipartite graph has two parts, with every possible edge between the parts and no edges within either part. When the part sizes differ, the larger part can often be left out of a small vertex cover, but every vertex of that larger part must still be included in an edge cover. Comparing these two kinds of cover makes the effect of unequal part sizes especially clear.
A matching is perfect if it covers every vertex. A matching is maximal if no edge can be added to it while keeping a matching; it is maximum if its size is as large as possible. These terms describe different properties in general, so the formulas below concern maximum matchings. For edge covers, a graph with an isolated vertex has no edge cover, because no edge is incident with that vertex. The empty graph has an edge cover consisting of no edges, of size zero.
Parameter Formulas
Proof. Let \(A,B\) be the two parts. For the vertex-cover number, each whole part is a vertex cover: every edge has one endpoint in each part. Thus \(\tau(K_{m,n})\leq\min(m,n)\). For the reverse inequality, consider any vertex cover \(C\). If \(C\) omits a vertex \(a\in A\), it must contain every vertex of \(B\): otherwise, an omitted \(b\in B\) would make the edge \(ab\) uncovered. Hence either \(C\) contains all of \(A\), or it contains all of \(B\). In either case \(|C|\geq\min(m,n)\), proving the formula for \(\tau\).
For an independent set \(I\), if it contains at least one vertex of \(A\), then it cannot contain any vertex of \(B\), since every cross-part pair is adjacent. In that case \(|I|\leq m\). If it contains no vertex of \(A\), then \(I\subseteq B\), so \(|I|\leq n\). Therefore \(|I|\leq\max(m,n)\). The larger part itself is independent, attaining that bound, so \(\alpha(K_{m,n})=\max(m,n)\).
A clique can contain at most one vertex from each part, since two distinct vertices in the same part are not adjacent. Thus every clique has size at most two. Because \(m,n>0\), there is an edge, whose two endpoints form a clique of size two. Therefore \(\omega(K_{m,n})=2\).
Every matching uses distinct vertices in each part, so it has at most \(m\) edges and at most \(n\) edges. Consequently \(\nu(K_{m,n})\leq\min(m,n)\). To attain this bound, suppose first that \(m\leq n\). List the vertices as \(A=\{a_1,\ldots,a_m\}\) and \(B=\{b_1,\ldots,b_n\}\). The edges \(a_1b_1,\ldots,a_mb_m\) form a matching of size \(m\), because all listed vertices are distinct and each such cross-part edge exists. If \(n<m\), pair \(b_i\) with \(a_i\) for \(1\leq i\leq n\), giving a matching of size \(n\). Hence \(\nu(K_{m,n})=\min(m,n)\).
A matching can cover every vertex only if the two parts have the same size, because each matching edge covers one vertex of each part. When \(m=n\), the construction just given pairs all vertices, so a perfect matching does exist. This proves both directions of the claim about perfect matchings.
Finally, suppose \(m\leq n\). Every edge covers only one vertex of \(B\), so any edge cover must have at least \(n\) edges: covering the \(n\) vertices of \(B\) requires at least \(n\) distinct edges. To attain this bound, use \(a_1b_1,\ldots,a_mb_m\) and then \(a_1b_j\) for every \(j\) with \(m<j\leq n\). These are \(m+(n-m)=n\) distinct edges, and together they cover every vertex. Thus \(\rho(K_{m,n})=n\) when \(m\leq n\). If \(n<m\), the same argument with the parts exchanged gives \(\rho(K_{m,n})=m\). Therefore \(\rho(K_{m,n})=\max(m,n)\). \(\square\)
Worked Examples
Worked Example: Unequal Parts in \(K_{2,5}\)
Let \(A=\{a_1,a_2\}\), \(B=\{b_1,b_2,b_3,b_4,b_5\}\), and \(E=\{a_i b_j:1\leq i\leq2,\ 1\leq j\leq5\}\). This explicitly lists the edge set by its rule: each of the two vertices in \(A\) is joined to each of the five vertices in \(B\). The graph has \(2+5=7\) vertices and \(2\cdot5=10\) edges.
The theorem gives \(\tau=\min(2,5)=2\), \(\alpha=\max(2,5)=5\), \(\omega=2\), \(\nu=\min(2,5)=2\), and \(\rho=\max(2,5)=5\). Concretely, \(A\) is a vertex cover of size \(2\), and \(B\) is an independent set of size \(5\). The edge \(a_1b_1\) is a clique of size \(2\), while no clique can be larger because it has at most one vertex from each part.
A maximum matching is \(\{a_1b_1,a_2b_2\}\). It has size \(2\), and no matching can have more than two edges because there are only two vertices in \(A\). A minimum edge cover is \(\{a_1b_1,a_2b_2,a_1b_3,a_1b_4,a_1b_5\}\). It covers both vertices in \(A\) and all five in \(B\), using five edges. Any edge cover needs at least five edges because each edge covers only one vertex of \(B\).Check: the displayed matching has two edges, the displayed edge cover has five, and these agree with the bounds from the part sizes.
Worked Example: Equal Parts in \(K_{4,4}\)
Let \(A=\{a_1,a_2,a_3,a_4\}\), \(B=\{b_1,b_2,b_3,b_4\}\), and \(E=\{a_i b_j:1\leq i\leq4,\ 1\leq j\leq4\}\). The graph has \(4+4=8\) vertices and \(4\cdot4=16\) edges.
Here \(\tau=\min(4,4)=4\), \(\alpha=\max(4,4)=4\), \(\omega=2\), \(\nu=\min(4,4)=4\), and \(\rho=\max(4,4)=4\). The set \(A\) is a vertex cover of size \(4\); the whole part \(B\) is an independent set of size \(4\). Any edge gives a two-vertex clique, and a clique cannot have three vertices because two of them would have to lie in the same part.
The matching \(\{a_1b_1,a_2b_2,a_3b_3,a_4b_4\}\) covers all eight vertices, so it is perfect. It is maximum because any matching contains at most four edges. The same four edges are an edge cover, and no edge cover can have fewer than four edges: its four vertices in \(B\) require four distinct incident edges. Check: the matching and edge cover each contain exactly \(4\) edges, and each covers all vertices required by its definition.
Worked Example: A Star \(K_{1,3}\)
Let \(A=\{a\}\), \(B=\{b_1,b_2,b_3\}\), and \(E=\{ab_1,ab_2,ab_3\}\). The graph has \(1+3=4\) vertices and three edges. Its parameters are \(\tau=\min(1,3)=1\), \(\alpha=\max(1,3)=3\), \(\omega=2\), \(\nu=\min(1,3)=1\), and \(\rho=\max(1,3)=3\).
The single vertex \(a\) is a vertex cover, and \(B\) is an independent set of size three. Each edge forms a clique of size two, and there can be no larger clique. A matching has at most one edge because all three edges share \(a\); any one edge is therefore a maximum matching. It is not perfect, since it covers only two of the four vertices. An edge cover must include all three edges: each leaf \(b_i\) is incident only with \(ab_i\). Thus all three edges form the unique edge cover, of size \(3\). Check: every leaf is covered exactly by its incident edge, confirming both that the three-edge set is an edge cover and that fewer edges cannot suffice.
Empty Parts and Common Mistakes
The theorem assumes both part sizes are positive, because then the graph has edges and no isolated vertices. If one part is empty and the other contains \(q>0\) vertices, \(K_{0,q}\) has no edges: all \(q\) vertices are isolated. Its vertex-cover number is \(0\), its independence number is \(q\), its clique number is \(1\), and its matching number is \(0\). It has no edge cover. If \(q=0\) as well, the graph has no vertices: the vertex-cover, independence, matching and edge-cover numbers are all \(0\), and we use \(\omega(K_{0,0})=0\). These conventions also explain why the positive-part formula \(\omega=2\) cannot be applied when an edge does not exist.
A common mistake is to confuse a feasible cover with a minimum cover. In \(K_{2,5}\), taking all five vertices of \(B\) does give a vertex cover, but it does not give a minimum one: taking \(A\) covers every edge using only two vertices. The correct lower bound comes from showing that any vertex cover must contain one whole part, not from counting the vertices of one chosen cover.
Another tempting but insufficient bound for an edge cover is \(\lceil |V|/2\rceil\), since one edge is incident with at most two vertices. For \(K_{2,5}\), this bound is \(\lceil 7/2\rceil=4\), but four edges cannot cover the five vertices of \(B\): each edge is incident with only one of them. The stronger requirement that the larger part needs a distinct incident edge for each of its vertices gives the correct minimum of \(5\).
For complete bipartite graphs with positive part sizes, every maximal matching is also maximum. Indeed, if a matching leaves at least one vertex unmatched in each part, the edge between those two vertices can be added, contradicting maximality. Thus a maximal matching must saturate one whole part and has size \(\min(m,n)\). This special property does not make “maximal” and “maximum” interchangeable in general graphs; the formula for \(\nu\) is established by the upper bound and construction in the proof.
Check Your Understanding
Use the two part sizes to justify each answer, and state when an edge cover does not exist.
- For \(K_{3,7}\), find \(\tau,\alpha,\omega,\nu\), and \(\rho\). Which part is a minimum vertex cover, and which is a maximum independent set?
- For \(K_{5,5}\), explain why a perfect matching exists and give one by listing its edges using part labels.
- Prove that a clique in \(K_{m,n}\), with \(m,n>0\), contains at most two vertices.
- For \(K_{0,4}\), find the vertex-cover, independence, clique and matching numbers. Explain why there is no edge cover.
- In a positive-part graph \(K_{m,n}\), explain why an edge cover has at least as many edges as the larger part has vertices.