My question is in the title but to restate:
Prove that a connected undirected graph $G$ is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for $G$. (BFS is short for breadth-first search.)
How would I go about proving this using induction? Is it even possible to prove using induction? I do not know where to start.
I guess induction is not a good idea here. There is a rather straightforward proof.
Let there be an edge between vertices $u$ and $v$ of the same level of BFS tree. Then there is obviously a cycle of odd length: let $w$ be the lowest common ancestor of $u$ and $v$, then cycle $u \leftrightsquigarrow w \leftrightsquigarrow v - u$ has an odd length (here $x \leftrightsquigarrow y$ is a $(x, y)$-path in BFS tree and $x - y$ is just an edge).
Let there be no edge between vertices of the same level of BFS tree. Suppose there is a cycle of odd length. Obviously it should have an edge between two vertices of levels that differ not by $1$. Then it should be at least $2$ since there is no edge between vertices of the same level. But any such edge contradicts to the way the tree was built, because edge between vertices $u$ and $v$ of levels that differ by at least $2$ implies that lower of $u$ and $v$ should go directly after higher of $u$ and $v$, i. e., higher than it actually is. This constradiction finishes the proof.