Definition:Complete Bipartite Graph

From ProofWiki
Jump to navigation Jump to search

Definition

A complete bipartite graph is a bipartite graph $G = \left({A \mid B, E}\right)$ in which every vertex in $A$ is adjacent to every vertex in $B$.

The complete bipartite graph where $A$ has $m$ vertices and $B$ has $n$ vertices is denoted $K_{m, n}$.

Note that $K_{m, n}$ is the same as $K_{n, m}$.


Examples

CompleteBipartiteGraphs.png


Basic Properties

  • $K_{1, n}$ = $K_{n, 1}$ is a tree for all $n$, and no other complete bipartite graphs are trees.
  • $K_{n, n}$ is $n$-regular for all $n$, and no other complete bipartite graphs are regular.
  • $K_{1, 1}$ and $K_{1, 2}$ are the path graphs $P_2$ and $P_3$ and no other complete bipartite graphs are path graphs.
  • $K_{1, 3}$ is known as a claw.