# Bipartite Graph

This is a more specific case of Graph Colouring with two colors.

A graph is bipartite if and only if it is two-colorable.

Odd cycle

A graph is bipartite exactly when it does not contain a cycle with an odd number of edge

### MATH239

Bipartite Graph

A graph is

bipartiteif its vertex set can be partitioned into two disjoint sets $A$, $B$ such that $V=A∪B$ and every edge in $G$ has one endpoint in $A$ and one endpoint in $B$.

Complete Bipartite Graph

For positive integers $m$, $n$, the complete bipartite graph $K_{m,n}$ is the graph with bipartition $A$, $B$ where $∣A∣=m$ and $∣B∣=n$, containing all possible edges joining vertices in $A$ with vertices in $B$.

$→$ Notice that there are $mn$ edges in $K_{m,n}$

**Theorems**

Theorem 5.3.2

A graph $G$ is bipartite $⟺$ it has no odd cycles.

#### How to Prove a Graph is Bipartite?

Create a bipartition, and show how the edges have one end in both sets.

- Proof done using Connectedness: