Bipartite and Complete Bipartite Graphs

Bipartite Graphs

Definition: A graph $G = (V(G), E(G))$ is said to be Bipartite if and only if there exists a partition $V(G) = A \cup B$ and $A \cap B = \emptyset$. Hence all edges share a vertex from both set $A$ and $B$, and there are no edges formed between two vertices in the set $A$, and there are not edges formed between the two vertices in $B$.

Here is an example of a bipartite graph (left), and an example of a graph that is not bipartite. Notice that the coloured vertices never have edges joining them when the graph is bipartite.

Screen%20Shot%202014-02-09%20at%2011.28.26%20PM.png

Complete Bipartite Graphs

Definition: A graph G = (V(G), E(G)) is said to be Complete Bipartite if and only if there exists a partition $V(G) = A \cup B$ and $A \cap B = \emptyset$ so that all edges share a vertex from both set $A$ and $B$ and all possible edges that join vertices from set $A$ to set $B$ are drawn.

We denote a complete bipartite graph as $K_{r, s}$ where $r$ refers to the number of vertices in subset $A$ and $s$ refers to the number of vertices in subset $B$. Below is an example of the complete bipartite graph $K_{5, 3}$:

Screen%20Shot%202014-02-09%20at%2011.38.05%20PM.png

Number of Vertices, Edges, and Degrees in Complete Bipartite Graphs

Since there are $r$ vertices in set $A$, and $s$ vertices in set $B$, and since $V(G) = A \cup B$, then the number of vertices in $V(G)$ is $\mid V(G) \mid = r + s$.

Additionally, the number of edges in a complete bipartite graph is equal to $r \cdot s$ since $r$ vertices in set $A$ match up with $s$ vertices in set $B$ to form all possible edges for a complete bipartite graph.

Lastly, if the set $A$ has $r$ vertices and the set $B$ has $s$ vertices then all vertices in $A$ have degree $s$, and all vertices in $B$ have degree $r$. This should make sense since each vertex in set $A$ connected to all $s$ vertices in set $B$, and each vertex in set $B$ connects to all $r$ vertices in set $A$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License