BFS two-coloring is the certificate that no odd cycle exists

A graph is bipartite when its vertices can be partitioned into two independent sets. Equivalently, the vertices admit a $2$-coloring in which every edge is bichromatic. 1. Prove that a graph $G$ is bipartite if and only if $G$ contains no odd cycle. For the forward direction, show that an odd cycle cannot be $2$-colored. For the converse, run breadth-first search independently in each connected component, color a vertex red or blue according to the parity of its BFS distance from the component root, and prove that a monochromatic edge would produce an odd closed walk and hence an odd cycle. 2. Let $G_0$ have vertex set $\{1,2,3,4,5,6,7\}$ and edge set \[ \{1{-}2,\ 1{-}3,\ 2{-}4,\ 2{-}5,\ 3{-}5,\ 3{-}6,\ 4{-}7,\ 5{-}7,\ 6{-}7\}. \] Run BFS from vertex $1$. Record the layer of every vertex, the resulting $2$-coloring, and the two color classes. Verify every edge of $G_0$ against that coloring, and conclude that $G_0$ is bipartite. The certificate must be the BFS layering, not an unspecified greedy coloring. 3. Let $H$ be the $5$-cycle on vertices $\{p,q,r,s,t\}$ with edges $pq,qr,rs,st,tp$. Run BFS from $p$, record colors by layer parity, and exhibit the first monochromatic edge that BFS detects. Extract an explicit odd cycle (the whole vertex set of $H$ is acceptable) and conclude that $H$ is not bipartite. 4. Audit the claim '$G_0$ has no triangles, therefore $G_0$ is bipartite' and the claim '$H$ contains a cycle, therefore $H$ is not bipartite'. Identify the missing length hypothesis. Do not treat an even cycle as an obstruction, and do not replace the BFS certificate by a matching argument or by Hall's theorem.

If a monochromatic edge $ab$ appears in a BFS coloring, the two rootward paths plus $ab$ form a closed walk whose length is odd because $\operatorname{dist}(a)$ and $\operatorname{dist}(b)$ have the same parity.