Complete Bipartite Graph¶
A bipartite graph K_{m,n} with no within-part edges and every possible edge between its two vertex parts present.
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
Everyone Meets the Other Team
Complete Bipartite Graph
Structural Signature¶
Sig role-phrases:
- Two vertex parts — Partition the graph vertices into U and V with declared cardinalities m and n. It is constitutive. Counterfactual: Without two disjoint parts, K_{m,n} has no defined bipartition.
- Within-part exclusion — Forbid edges between vertices in the same part. It is constitutive. Counterfactual: An added edge inside U or V defeats bipartiteness.
- Cross-part saturation — Include every one of the m n possible U-to-V edges. It is constitutive. Counterfactual: Removing one cross edge leaves a bipartite, possibly biregular, graph but not a complete bipartite graph.
- Part-size notation — Records the graph as K_{m,n} up to interchange of the parts. It is diagnostic. Counterfactual: A bare graph label without part sizes cannot identify its isomorphism class.
What It Is Not¶
- Not every bipartite graph. The two parts must be joined by every possible cross edge.
- Not a complete graph. Within-part edges are absent when the relevant part has multiple vertices.
- Not a biclique subgraph claim. The classified graph itself must satisfy the full partition, unless a subgraph is explicitly named.
- Not universally nonplanar. K_{3,3} is nonplanar, whereas stars are planar.
- Closest near-miss. A graph that contains a K_{3,3} on six selected vertices may still have extra vertices or edges, so its full graph is not thereby K_{3,3}.
Scope of Application¶
- 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¶
State the two nonempty vertex parts and verify zero internal edges and exactly m n cross edges. A graph with one absent cross edge remains bipartite but is not complete bipartite; a K_{3,3} subgraph does not classify the entire host graph. Name the part sizes before using size-dependent planarity or matching facts.
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¶
- Choose a proposed split U and V covering every vertex.
- Check that no edge has both ends on one side.
- Check each cross-part pair, or equivalently count m n distinct cross edges in a simple graph.
- Report the K_{m,n} isomorphism class up to part exchange.
- 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.
Examples¶
Canonical¶
K_{2,3} has two vertices on one side and three on the other, all six cross pairs joined, and no within-side edge. Deleting any one of those six edges makes the resulting graph incomplete bipartite.
Mapped back: Two vertex parts → parts of sizes two and three; Within-part exclusion → zero same-side edges; Cross-part saturation → all 2 × 3 cross pairs present; Part-size notation → K_{2,3}.
Applied / In Practice¶
The source's K_{3,3} utility graph joins each of three buildings to each of three utilities. Its nonplanarity is a consequence for this size, not a criterion that turns every nonplanar graph into a biclique.
Mapped back: Two vertex parts → three buildings versus three utilities; Within-part exclusion → no building-building or utility-utility edge; Cross-part saturation → all nine requested connections; Part-size notation → K_{3,3}.
Structural Tensions¶
T1 — Bipartite Exclusion versus Cross-Part Completeness. The same partition forbids all same-side edges while demanding all other possible edges; relaxing either side changes the graph class.
Diagnostic: Is every permitted edge present and every forbidden edge absent?
T2 — Local Edge Test versus Global Graph Identity. One observed biclique inside a larger graph does not mean the whole vertex set is K_{m,n}.
Diagnostic: Does the proposed partition cover every vertex of the graph being classified?
Structural–Framed Character¶
The approved DAG parent is Biregular Graph: vertices on one side have uniform degree n and on the other degree m. Completeness adds every cross-part edge and excludes within-part edges, defining K_{m,n} for positive part sizes.
Evaluative weight: Low; “complete” denotes edge saturation, not social desirability. Human-practice-bound: Low formally, though a modeler chooses what relations count as edges. Institutional origin: Graph theory fixes notation and definition, not membership by authority. Vocabulary travels: The test applies to any modeled two-part relation with all cross pairs linked. Import versus recognize: Recognize K_{m,n} by an explicit graph partition and edge set; a vague “everyone connected” claim imports unsupported adjacency.
Its character: A formal graph subtype with a portable exhaustive-incidence idea and exact vertex–edge semantics.
Structural Core vs. Domain Accent¶
Skeletal core. Two disjoint kinds have exhaustive cross-type incidence and no same-type incidence.
Domain-bound accent. In a simple graph, two nonempty vertex parts have every possible cross edge; K_{m,n} fixes their sizes and isomorphism type.
Why not prime. All-to-all rhetoric outside an explicit graph model lacks the exact adjacency and exclusion conditions.
Instantiates / Related Primes¶
This entry is a kind of Biregular graph.
-
Strict parent — Biregular graph. Every U vertex has degree n and every V vertex degree m, so every nondegenerate K_{m,n} is biregular; the converse can omit cross edges.
-
Related — bipartite graph, star, claw, and utility graph. Bipartiteness is broader; the others are named size-specific instances.
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.Each complete bipartite K_{m,n} has degree n at every vertex of its m-side and degree m at every vertex of its n-side, meeting the live biregular graph's two-uniform-side-degree signature. Biregularity need not saturate all cross pairs, so completeness is the child's strict differentia.
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 (36th 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
Not to Be Confused With¶
- Bipartite graph. Tell: Does it include every permitted cross edge?
- Complete graph. Tell: Are same-side edges absent?
- Biclique subgraph. Tell: Does the claimed partition cover the host graph or only selected vertices?
- Biregular graph. Tell: Do uniform side degrees reach the opposite part's full size?
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Complete_bipartite_graph (revision 1352460132).
- Preserved source candidate: https://archive.org/details/graphtheorywitha0000bond/page/5
- Preserved source candidate: http://diestel-graph-theory.com/
- Preserved source candidate: https://books.google.com/books?id=vj1oAgAAQBAJ&pg=PA7
- Preserved source candidate: https://books.google.com/books?id=yW3WSVq8ygcC&pg=PA109
- Preserved source candidate: https://books.google.com/books?id=ZWTDQ6H6gsUC&pg=PA437
- Preserved source candidate: https://archive.org/details/computersintract0000gare/page/196
- Preserved source candidate: https://books.google.com/books?id=6TasRmIFOxQC&pg=PA181
- Preserved source candidate: https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA104
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.