0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ This is not really an answer. You are basically saying that the question is a "very well-known fact". $\endgroup$ – Thomas Lesgourgues Apr 8 at 9:08
  • $\begingroup$ Below comment is addtional... $\endgroup$ – Dong-gyu Kim Apr 8 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.