Complete bipartite graph

1 Basic definition and notation

1.1 Bipartite graphs and vertex partitions

A bipartite graph is a graph whose vertex set can be split into two disjoint classes so that every edge connects a vertex from the first class to a vertex from the second class. In a complete bipartite graph, this “every allowed cross-edge exists” condition is maximized.

1.2 Edge structure of \(K_{m,n}\)

The complete bipartite graph \(K_{m,n}\) consists of two disjoint vertex sets \(A\) and \(B\) with \(	A	=m\) and \(	B	=n\). Every vertex in \(A\) is connected to every vertex in \(B\). There are no edges inside \(A\) and no edges inside \(B\).

1.3 Notation, labeling, and examples

The notation \(K_{m,n}\) emphasizes the sizes of the two parts. Commonly, vertices are labeled as \(A=\{a_1,\dots,a_m\}\) and \(B=\{b_1,\dots,b_n\}\), with the edge set \[ E(K_{m,n})=\{a_i b_j : 1\le i\le m,\; 1\le j\le n\}. \] Examples include \(K_{1,n}\) (a star), \(K_{2,2}\) (a 4-cycle), and \(K_{2,3}\) (a “ladder-like” bipartite structure).

2 Structural properties

2.1 Degree sequences and adjacency

2.1.1 Degree of vertices in each part

All vertices in the part \(A\) have the same degree, equal to the number of vertices in \(B\), namely \(n\). Similarly, every vertex in \(B\) has degree \(m\). Thus \(K_{m,n}\) has a highly uniform degree sequence:

\(m\) vertices of degree \(n\),
\(n\) vertices of degree \(m\).

2.1.2 Edge count \(mn\)

Because every pair \((a_i,b_j)\) forms an edge, the number of edges is \[

E(K_{m,n})	=mn.

2.2.1 Relation to independent sets

In \(K_{m,n}\), each part \(A\) and \(B\) is an independent set: there are no edges among vertices within the same part. Conversely, any graph complement relationship can be described by noting that the only missing edges inside the parts become present in the complement.

2.2.2 Relation to complete graphs in special cases

While \(K_{m,n}\) is not generally a complete graph, it becomes complete in a trivial sense when one part has size \(1\): then \(K_{1,n}\) is a complete bipartite graph and resembles a star, and the overall graph is complete bipartite rather than complete in the usual single-part sense. The complete-graph connection arises more meaningfully in the complements and in special parameter choices, but the defining property remains bipartite completeness.

2.3 Symmetry and automorphisms

The graph has strong symmetry. Any permutation of the vertices within \(A\) that respects adjacency can be combined with any permutation within \(B\), producing an automorphism. In particular, the automorphism group contains all permutations of \(A\) and all permutations of \(B\), reflecting the fact that vertices within a part are structurally indistinguishable.

3 Fundamental invariants

3.1 Order, size, and basic parameters

The order of \(K_{m,n}\) (total number of vertices) is \[ m+n, \] and the size (number of edges) is \(mn\). The graph is simple, finite, and its bipartition is given by the construction.

3.2 Diameter and eccentricity

If \(m,n \ge 1\), any two vertices from opposite parts are adjacent, so their distance is \(1\). Two vertices within the same part cannot be adjacent, but they both connect to every vertex of the other part, giving a path of length \(2\) between them. Hence:

the diameter is \(1\) only in the degenerate case where one part has size \(0\) (usually excluded) and
for positive \(m,n\), the diameter of \(K_{m,n}\) is \(2\).

Eccentricity values mirror this: vertices in the same part have maximum distance \(2\) to each other.

3.3 Girth and cycle structure

3.3.1 Existence of 4-cycles and \(K_{2,2}\)

The girth is the length of the shortest cycle. In \(K_{m,n}\), there are no triangles because the graph is bipartite. The smallest possible cycle is length \(4\). A 4-cycle occurs exactly when both parts have at least two vertices: \(K_{2,2}\) is itself a 4-cycle, and \(K_{m,n}\) contains copies of \(K_{2,2}\) whenever \(m\ge2\) and \(n\ge2\). Therefore, for \(m,n\ge2\) the girth is \(4\).

4 Connectivity and separation

4.1 Vertex connectivity \(\kappa(K_{m,n})\)

Vertex connectivity measures the minimum number of vertices whose removal disconnects the graph. For complete bipartite graphs with \(m,n\ge 2\), removing all vertices from the smaller side isolates what remains, and a standard result is that \[ \kappa(K_{m,n})=\min(m,n). \] This reflects that vertices in the smaller part are “bottlenecks” for keeping both sides connected.

4.2 Edge connectivity \(\lambda(K_{m,n})\)

Edge connectivity is the minimum number of edges whose removal disconnects the graph. For \(m,n\ge 1\), the edge connectivity equals the degree of any vertex in the smaller part, giving \[ \lambda(K_{m,n})=\min(m,n). \] Because the graph is highly interwoven between parts, the minimal disconnection is achieved by focusing on all edges incident to vertices in the smaller side.

4.3 Cut sets and minimal separations

A cut set can be described using the bipartition: removing a set of vertices from one side can drastically reduce the available cross edges. Minimal separations align with the minimum values \(\min(m,n)\), since that is the smallest “amount of structure” required to break the ability to travel across.

4.4 Minimal vertex covers (structural viewpoint)

A vertex cover is a set of vertices meeting every edge. In \(K_{m,n}\), any complete selection of one part (all vertices in \(A\) or all vertices in \(B\)) is a vertex cover, since every edge touches both parts. However, smaller covers may exist when \(m\) and \(n\) are unbalanced, and the minimal size is related to maximum matching size (a theme clarified in the next section).

5 Matchings and coverings

5.1 Hall’s marriage theorem for \(K_{m,n}\)

Hall’s marriage theorem provides a criterion for when a bipartite graph has a matching that saturates one part. For \(K_{m,n}\), the condition is automatically satisfied as long as the target side is not larger than the other: any subset \(S\subseteq A\) has neighborhood \(N(S)=B\), so \(	N(S)	=n\). Thus:

a matching saturating \(A\) exists iff \(m\le n\),
a matching saturating \(B\) exists iff \(n\le m\).

5.2 Maximum matchings and conditions

The maximum size of a matching in \(K_{m,n}\) is \[ \min(m,n), \] since each matched edge uses one vertex from each part, and no vertex can be reused in a matching. The construction is straightforward: match every vertex of the smaller part to distinct vertices in the larger part.

5.3 Perfect matchings and when they exist

A perfect matching covers all vertices. Therefore, \(K_{m,n}\) admits a perfect matching exactly when \(m=n\). In that case, one can pair each vertex of \(A\) with a distinct vertex of \(B\) in many ways because every cross-edge is available.

5.4 Edge covers and vertex covers

5.4.1 Minimum vertex cover size via structure

For bipartite graphs, Kőnig’s theorem states that the size of a minimum vertex cover equals the size of a maximum matching. Applying this to \(K_{m,n}\), the minimum vertex cover size is \[ \min(m,n). \] Structurally, one can realize such a cover by taking all vertices from one part of size \(\min(m,n)\) in appropriate cases, though additional optimal covers may also exist depending on symmetry.

6 Coloring and chromatic parameters

6.1 Chromatic number of \(K_{m,n}\)

Because \(K_{m,n}\) is bipartite, it can be colored using two colors by assigning distinct colors to the two parts. When both parts are nonempty, the chromatic number is \[ \chi(K_{m,n})=2. \] If one part is empty (typically excluded), the graph has chromatic number \(1\).

6.2 Proper coloring construction

A proper 2-coloring assigns one color to all vertices in \(A\) and a different color to all vertices in \(B\). This works because every edge runs between parts, never within a part.

6.3 Chromatic polynomial (high-level behavior)

The chromatic polynomial \(P_G(k)\) counts the number of proper colorings using \(k\) colors. For \(K_{m,n}\), a high-level description is that proper colorings correspond to assignments where adjacent vertices (which are all cross-part pairs) never share a color. One can think of choosing a coloring of \(A\) and then selecting colors for \(B\) from the colors not used by each vertex in \(A\); due to complete cross adjacency, the constraints are strong and the resulting count can be expressed in closed form using inclusion–exclusion. The key conceptual point is that the bipartite structure makes the polynomial tractable.

6.4 Bicoloring and constraints from bipartiteness

Any proper coloring using exactly two colors forces all vertices in \(A\) to use one color and all vertices in \(B\) to use the other, up to swapping colors. This rigidity comes from the fact that every vertex in \(A\) is adjacent to every vertex in \(B\), so if two vertices across the bipartition shared a color, it would violate properness.

7 Cycles, paths, and subgraphs

7.1 Hamiltonicity questions (general discussion)

Hamiltonicity asks whether a graph contains a cycle visiting every vertex exactly once. For complete bipartite graphs, Hamiltonian behavior depends on parity and balance between \(m\) and \(n\). A cycle in a bipartite graph must alternate between parts, so the cycle length is constrained by how many vertices each part contributes. This often yields simple necessary conditions, while sufficiency can be verified using constructive arguments exploiting the “all edges present” property.

7.2 Counting common small subgraphs

7.2.1 Counting 4-cycles in \(K_{m,n}\)

A 4-cycle in \(K_{m,n}\) corresponds to choosing two distinct vertices from \(A\) and two distinct vertices from \(B\), then traversing them in an alternating order. Each choice of \(\{a_i,a_{i'}\}\subseteq A\) and \(\{b_j,b_{j'}\}\subseteq B\) yields a subgraph isomorphic to \(K_{2,2}\), which contains exactly one 4-cycle up to direction in an unlabeled sense. Counting distinct cycles in the labeled graph leads to \[ \#C_4 = \binom{m}{2}\binom{n}{2}. \] This formula highlights how cycles are governed by combinatorial selections of vertex pairs from each part.

7.3 Induced subgraphs and embeddings

Any induced subgraph obtained by taking subsets \(A'\subseteq A\) and \(B'\subseteq B\) is again a complete bipartite graph \(K_{	A'	,	B'	}\). This self-similarity simplifies many extremal and embedding arguments, because the induced structure remains “complete” across the bipartition.

7.4 Extremal subgraph observations

Because \(K_{m,n}\) contains every possible cross-edge, it maximizes edge density among bipartite graphs with the same parts. Consequently, it tends to maximize the number of many bipartite substructures (like 4-cycles) and provides extremal examples in problems seeking the largest number of certain bipartite configurations.

8 Algebraic and spectral aspects

8.1 Adjacency matrix block form

With the bipartition ordered as \(A\) followed by \(B\), the adjacency matrix of \(K_{m,n}\) has a block form: \[ \begin{pmatrix} 0 & J_{m\times n}\\ J_{n\times m} & 0 \end{pmatrix}, \] where \(J\) denotes an all-ones matrix of the indicated dimensions.

8.2 Eigenvalues in terms of \(m\) and \(n\)

The spectrum follows from the rank-structure of the all-ones blocks. The nonzero eigenvalues are \[ \sqrt{mn},\quad -\sqrt{mn}, \] and the remaining \(m+n-2\) eigenvalues are \(0\). This reflects that the adjacency matrix has low effective rank due to the uniform adjacency pattern.

8.3 Rank and linear-algebraic consequences

8.3.1 Incidence-style interpretations

The low rank implied by the spectrum ties to the idea that adjacency relations factor through “which part” a vertex belongs to. In linear-algebra terms, many walk-counting and mixing phenomena can be expressed compactly using the principal eigenvectors associated with \(\pm\sqrt{mn}\), while the rest of the space corresponds to eigenvalue \(0\).

9 Enumeration and combinatorial interpretations

9.1 Number of edges between parts

The basic enumeration is immediate: every vertex in \(A\) connects to every vertex in \(B\), giving \(mn\) cross edges. Many counting tasks for subgraphs in \(K_{m,n}\) reduce to counting ways to choose vertices from each part, then accounting for complete adjacency.

9.2 Counting matchings (overview)

Counting matchings of a given size \(t\) in \(K_{m,n}\) can be approached by selecting \(t\) vertices from \(A\), selecting \(t\) vertices from \(B\), and then counting the bijections between them (since a size-\(t\) matching uses a distinct partner in the other part for each chosen vertex). This yields a closed-form expression in terms of binomial coefficients and factorial terms.

9.3 Counting spanning trees (parameterized results)

The number of spanning trees in \(K_{m,n}\) is known and admits a compact formula derived via the matrix-tree theorem and the special block form of the Laplacian. The high-level point is that symmetry makes the computation manageable: eigenvalues of the Laplacian can be determined explicitly, and the product of nonzero Laplacian eigenvalues produces the count.

9.4 Applications to counting problems

Complete bipartite graphs serve as benchmark cases for counting problems. Because many subgraphs correspond to selecting small subsets from each part and exploiting complete adjacency, they become natural reference points for testing conjectures, calibrating bounds, and validating enumeration techniques.

10 Variants and generalizations

10.1 Balanced vs. unbalanced \(K_{n,n}\) vs. \(K_{m,n}\)

When \(m=n\), the graph is balanced: many properties become more symmetric and perfect structures (such as perfect matchings) exist. In unbalanced cases, maximum matchings saturate only the smaller side, and some “global” equal-coverage phenomena fail or require modified formulations.

10.2 Complete multipartite graphs (brief extension)

A natural extension is the complete multipartite graph: vertices are partitioned into more than two parts, and edges are present between every pair of different parts, with none within a part. Many structural themes from \(K_{m,n}\) generalize, including degree patterns, connectivity behavior, and spectrum methods based on block matrices.

Regular bipartite graphs have uniform degrees on both sides but do not necessarily contain all cross edges. They share some bipartite constraints and often resemble \(K_{m,n}\) in extremal or algorithmic roles, yet their lack of complete adjacency makes counting and spectral computations more involved.

10.4 Multigraph or weighted variants (conceptual)

One can generalize to multigraphs by allowing multiple edges between a pair of vertices across the bipartition, or to weighted graphs where edge weights vary. Conceptually, many results extend by replacing adjacency counts with weighted sums, though exact formulas may change.

11 Common theorems and problem-solving strategies

11.1 Using bipartite structure to simplify proofs

Many arguments become simpler because bipartiteness eliminates odd cycles and forces alternating behavior in paths and cycles. Additionally, completeness across parts means that neighborhoods are easy to compute: the neighbor set of any vertex is the entire opposite part.

11.2 Typical exam-style lemmas for \(K_{m,n}\)

Common useful facts include:

degrees are constant within each part,
diameter is \(2\) for positive \(m,n\),
there are no triangles,
cycle length constraints (smallest cycle length is \(4\) when both parts have size at least \(2\)),
maximum matching size is \(\min(m,n)\),
chromatic number is \(2\),
vertex/edge connectivity equals \(\min(m,n)\).

These lemmas often combine quickly to solve standard tasks on matchings, coloring, and connectivity.

11.3 Worked example templates (degree, matching, coloring)

A typical workflow:

Degree-based questions: use that every vertex in \(A\) has degree \(n\) and every vertex in \(B\) has degree \(m\).
Matching questions: apply the fact that any matching uses distinct vertices in both parts, so the best possible size is \(\min(m,n)\); check balance for perfect matchings.
Coloring questions: use bipartiteness to propose a 2-coloring; then argue minimality when both parts are nonempty.