# Help formulating a conjecture about the parity of every cycle length in a bipartite graph and proving it

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.

## 2 Answers

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

• A graph $$G$$ is bipartite iff every cycle in $$G$$ is even.
• This is not really an answer. You are basically saying that the question is a "very well-known fact". – Thomas Lesgourgues Apr 8 at 9:08
• Below comment is addtional... – Dong-gyu Kim Apr 8 at 9:17