Complete Bipartite Graph

A bipartite graph K_{m,n} with no within-part edges and every possible edge between its two vertex parts present.

Version

v1 · 2026-09-28 · History

Domain-specific #

8595

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomain

Graph Theory → Mathematics

Aliases

Biclique, K {m,n}

Core Idea

A complete bipartite graph joins every vertex in one nonempty part to every vertex in another and joins no two vertices within either part. The partition and full cross-edge set, not a drawing style, define the graph. With positive part sizes m and n it is denoted K_{m,n} and has m n edges.

Stars and the utility graph are particular sizes of this one structure. Complete bipartiteness is stronger than bipartiteness or side-uniform degrees: a single missing cross edge breaks completeness. Properties such as nonplanarity depend on the size and are not universal identity conditions.

How would you explain it like I'm…

Two-Team Handshakes

Picture two teams standing across from each other. Every player shakes hands with every player on the other team, but nobody shakes hands with their own teammates. That exact pattern of handshakes is a complete bipartite graph.

Everyone Meets the Other Team

A graph is a set of dots joined by lines. In a complete bipartite graph, the dots are split into two groups, each with at least one dot. Every dot in one group is joined to every dot in the other group, and no two dots in the same group are joined. If one group has m dots and the other has n, there are m times n lines. Even one missing line between the groups means it is no longer complete.

Complete Bipartite Graph

A complete bipartite graph splits its vertices into two nonempty parts and connects every vertex in one part to every vertex in the other, with no edges inside either part. With part sizes m and n it is written K_{m,n} and has exactly m·n edges. What defines it is the partition and the full set of cross edges, not how it's drawn. This is stronger than just being bipartite (which only forbids edges inside each part) and stronger than every vertex on a side having the same degree: a single missing cross edge breaks completeness. Stars (one part of size 1) and the utility graph K_{3,3} are particular sizes of this one structure.

 

A complete bipartite graph has its vertex set partitioned into two nonempty parts, with an edge between every vertex of one part and every vertex of the other and no edges within either part. For positive part sizes m and n it is denoted K_{m,n} and has exactly mn edges. The identity lies in the partition together with the complete cross-edge set, not in any drawing. Complete bipartiteness is strictly stronger than bipartiteness, and also stronger than simply having every vertex on a side share the same degree: removing a single cross edge breaks it. Stars and the utility graph are particular sizes of this one family. Properties such as nonplanarity hold only for certain sizes, so they are not part of what makes a graph complete bipartite.

Scope of Application

These uses retain the exact two-part all-cross-edge graph identity.

• Graph classification. Recognizes a full K_{m,n} from its bipartition and edge set.
• Extremal examples. Uses K_{3,3} and stars as size-dependent witnesses.
• Relation modeling. Represents all-to-all links between two types of entity.
• Algorithmic graph work. Distinguishes full biclique identity from searching for biclique subgraphs in a larger graph.

Clarity

Name the two vertex parts and check that no same-part edges and all m n cross edges exist. Include the whole graph K_{m,n}; exclude a merely bipartite graph missing one permitted edge or a host containing only a biclique subgraph. K_{3,3} is a nonplanar size-specific case, while a star K_{1,n} is planar. Neither property defines all complete bipartite graphs.

Manages Complexity

K_{m,n} compresses an adjacency list into one partition and an all-cross-pairs rule. That compression licenses exact edge counts and degree consequences, but only after checking that the assertion concerns the whole graph rather than one dense subgraph.

Abstract Reasoning

1. Choose a proposed split U and V covering every vertex.
2. Check that no edge has both ends on one side.
3. Check each cross-part pair, or equivalently count m n distinct cross edges in a simple graph.
4. Report the K_{m,n} isomorphism class up to part exchange.
5. Use size-dependent properties only after the identity and m,n values are fixed.

Knowledge Transfer

The two-part all-to-all adjacency test transfers literally to any graph-theoretic relation between two typed sets when every permitted pair is linked. A merely dense relation, a missing cross pair, or a general social claim of complete connection is not K_{m,n} unless the same graph carrier and edge rule are specified.

Relationships to Other Abstractions

Current abstraction Complete Bipartite Graph Domain-specific

Parents (1) — more general patterns this builds on

• Complete Bipartite Graph is a kind of Biregular graph Domain-specific

  K_{m,n} has uniform degree n on one side and m on the other, strictly specializing a biregular bipartite graph.

Hierarchy path (1) — routes to 1 parentless root

• Complete Bipartite Graph → Biregular graph → Symmetry

Neighborhood in Abstraction Space

Complete Bipartite Graph sits in a crowded region of the domain-specific corpus (36^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Structures & Algorithms (24 abstractions)

Nearest neighbors

• Utility graph — 0.91
• Sierpiński Graph — 0.89
• Prism graph — 0.89
• Total graph — 0.88
• Double-Pushout Graph Rewriting — 0.88

Computed from structural-signature embeddings · 2026-10-08