Bipartite Graph | Sahithyan's Notes

A graph where vertices can be split into disjoint sets $V_1$ and $V_2$ such that:

All edges go between $V_1$ and $V_2$ ,
No edges exist inside $V_1$ or inside $V_2$ .

Complete graphs are not bipartite.

If a graph contains a cycle of odd length, it is not bipartite.

Subgraph of a bipartite graph is also bipartite.

Proof Hint

Suppose $G$ has $G_1$ and $G_2$ biparitions. And $H$ be a subgraph of $G$ .
Every edge in $G$ has one endpoint in $G_1$ and other in $G_2$
$V(H) \subseteq V(G)$
Suppose $A = G_1 \cap V(H)$ and $B = G_2 \cap V(H)$
$A$ and $B$ are a valid parition pair.

A' = A \cap V(H), \qquad B' = B \cap V(H)

Claim: $(A', B')$ is a valid bipartition of $H$ .

Verification

(1) They partition $V(H)$ : Since every vertex of $H$ belongs to $V \subseteq A \cup B$ , it lies in exactly one of $A'$ or $B'$ . So $A' \cup B' = V(H)$ and $A' \cap B' = \emptyset$ . ✓

(2) Every edge of $H$ goes between $A'$ and $B'$ :

Take any edge $e = (u, v) \in E(H)$ . Since $E(H) \subseteq E$ , this edge also belongs to $G$ . Since $G$ is bipartite with partition $(A, B)$ , one endpoint lies in $A$ and the other in $B$ — say $u \in A$ , $v \in B$ .

Since $u \in V(H)$ and $u \in A$ , we have $u \in A'$ . Similarly, $v \in B'$ .

So every edge of $H$ crosses between $A'$ and $B'$ . ✓

Conclusion

$H$ admits the bipartition $(A', B')$ , so $H$ is bipartite. $\blacksquare$

Bipartition Set

The disjoint sets ( $V_1$ and $V_2$ ) in the above process.

Complete Bipartite Graph

Every vertex in $V_1$ is connected to every vertex in $V_2$ . Denoted by $K_{m,n}$ . $m,n \in \mathbb{N}$ .

Has $m \times n$ edges.