📂Graph Theory

Bipartite Graph

Definition ¹

A graph $G$ is called a bipartite graph and is also represented as $G = G(A,B)$ if there exists a partition $\left\{ A,B \right\}$ of the vertices $V(G)$ such that for every $xy \in E(G)$, it is either $x \in A, y \in B$ or $x \in B , y \in A$.

Explanation

As the name suggests, a bipartite graph is a graph where the vertices are divided into two groups, and there are no adjacent vertices within the same group. For example, in the following diagram, orange vertices are not adjacent to each other, and neither are the blue vertices.

As seen, being in different partitions doesn’t necessarily mean they have to be adjacent. If they are, it’s called a Complete Bipartite Graph. If the partition is made into three sets, it’s called a Tripartite Graph. Naturally, it’s possible to generalize to $n$ partitions, but usually, bipartite graphs are sufficient for research purposes.

Meanwhile, the following theorem related to cycles is known for bipartite graphs.

Theorem

Let $G$ be a connected graph. That $G$ is a bipartite graph is equivalent to the length of every cycle in $G$ being even.

Proof

$(\Rightarrow)$

Let’s assume $G = G(A,B)$ is a bipartite graph. If a cycle in $G$ starts at a vertex in $A$, it must move to $B$ and then back to $A$ through two edges. So, no matter how many times it goes to $B$, to form a closed path, it must always cross an even number of edges. Therefore, all cycles in $G$ must have even lengths.

---

$(\Leftarrow)$

Let’s fix one vertex $v \in V(G)$ in $G$. group all vertices with the shortest path from $v$ to $w$ into a set $A \subset V(G)$ whose length is even, and group the others into a set as $B := V(G) \setminus A$. If two vertices $a_{1}$ and $a_{2}$ in $A$ are adjacent, then the length of the cycle $$ v \to \cdots \to a_{1} \to a_{2} \to \cdots \to v $$ according to the definition of $A$, becomes odd. However, since the length of every cycle in $G$ is even by assumption, this is a contradiction, and thus vertices in $A$ cannot be adjacent. The same applies to vertices in $B$. Therefore, $G$ must be a bipartite graph $G(A,B)$.

■