Bipartite Graphs

Definition

Let $G$ be a connected graph, and let $L_0,\cdots ,L_k$ be the layers produced by BFS starting at node $s$. Exactly one of the following holds,

1. No edge of $G$ joins two nodes of the same layer, and $G$ is bipartite.
2. An edge of $G$ joins two nodes of the same layer, and $G$ contains an odd_legth cycle.