Complement of Complete Bipartite Graph
Jump to navigation
Jump to search
Theorem
Let $K_{p, q}$ be a complete bipartite graph.
The complement of $K_{p, q}$ consists of a disconnected graph with two components:
- The complete graph $K_p$
- The complete graph $K_q$.
Proof
By definition, the complete bipartite graph $K_{p, q}$ consists of two sets of vertices: $A$ of cardinality $p$, and $B$ of cardinality $q$, such that:
The complement of $K_{p, q}$ therefore must be a graph $G$ such that:
The second and third of these conditions describes the complete graphs $K_p$ and $K_q$.
From the first of these conditions, it follows that $G$ comes in two disconnected graph components.
Hence the result.
$\blacksquare$