I know a cycle in a graph $G=(V,E)$ is a sequence of vertices $$v_0, v_1,\ldots, v_k$$ such that $k\geq 3$, $v_k = v_0$, and $G$ contains every edge between consecutive vertices: $(v_0, v_1)$, $(v_1, v_2), \ldots$, $(v_{k−1}, v_k)$. I know eventually I want to prove any cycle in a bipartite graph has an even length as the conjecture.
A hint has been given to use simple induction, but I am having trouble proving a bipartite graph with length $k+1$ also can only contain cycles of even length.
On
If you want to prove that every cycle in a bipartite graph is even, you can reason by contradiction. In details :
Let $G$ be a bipartite graph with sets of vertices $V_0$ and $V_1$. Suppose now that you have an off cycle in $G$, of length $2k+1$ : $$ v_0,v_1,\ldots,v_{2k}$$
Without loss of generality you can suppose that $v_0\in V_0$. Then $v_1$ must be in $V_1$, $V_2$ in $V_0$, etc. Formally $v_i\in V_0$ if and only if $v_{i+1}\in V_1$, or $v_i\in V_0$ if and only $i$ is even.
This implies that $v_{2k}$ is in $V_0$. Then we have $$ \left\{ \begin{array}{l} v_{0}\in V_0\\ v_{2k}\in V_0 \end{array}\right.\text{ and } (v_{2k},v_0)\in E(G)$$
A contradiction with the fact that $G$ is bipartite.
I don't know why we need to use an induction. The problem: every cycle in a bipartite graph is even, is simply proved by a contradiction.
Assume that there is an odd cycle in a bipartite graph. However, this derives a contradiction from two facts: 1. any subgraph of a bipartite graph is bipartite, and 2. odd cycle is not a bipartite graph.
It is very well-known fact that