Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that: a simple graph is a bipartite graph if and only if lenght of all circuits in graph be even. (give me answer or hint or idea)

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

One direction is very easy. Here’s an extended hint for the other direction.

Let $G$ be a graph with no odd cycles. We may as well assume that $G$ is connected; otherwise we just work with the components of $G$ individually. Let $V$ be the vertex set of $G$, and for each $v\in V$ let $N(v)$ be the set of vertices adjacent to $v$.

Pick any vertex $v_0$, and let $V_0=\{v_0\}$. Given $V_n$ for some $n\in\Bbb N$, let $$V_{n+1}=\left(\bigcup_{v\in V_n}N(v)\right)\setminus\bigcup_{k\le n}V_k\;;$$ $V_{k+1}$ is the set of vertices adjacent to $V_n$ that haven’t already been put into one of the sets $V_k$.

Now let $V_{\text{odd}}$ be the union of the sets $V_{2k+1}$ and $V_{\text{even}}$ be the union of the sets $V_{2k}$, and show that $V_{\text{odd}}$ and $V_{\text{even}}$ form a bipartition of $V$. To do this, you’ll need to show that an edge within one of these two sets would create an odd cycle in $G$.

share|improve this answer
add comment

It is easy to see that if $G$ contains an odd cycle then it is not bipartite since you cannot color and odd cycle with only 2 colors.

So suppose $G$ is a bipartite graph. Consider a BFS tree $T$ of $G$ rooted at some vertex $v \in V(G).$ Color the vertices of $T$ with blue color if they are at odd distance from $v$ in $T$ and with red color otherwise.

Now we claim that this is a proper coloring of $G.$ For if it is not then two blue (or red) vertices are adjacent in $G$ which creates an odd cycle in $G$ since vertices of the same color have equal parity and the additional edge joining two of them makes an odd cycle in $G.$

Edit. If you do not wish to say this is a proper coloring you can rephrase the following part as follows. Let $A$ be the set of all vertices at even distance from $v$ and let $B = V(G)\setminus A.$ We claim that this is a bipartition for $G$. For if it is not then two vertices in $A$ or $B$ are adjacent but this implies there exist an odd cycle since vertices from $A$ (or $B)$ are at distance of equal parity and the additional edge creates a cycle of odd parity.

share|improve this answer
    
can you prove it without coloring and trees?(thank for help) –  World Oct 23 '12 at 20:31
    
You can simply say that vertices at odd distance from $v$ form one bipartition of $G$ and vertices at even distance the other bipartition. Then you use the same argument with the even cycle. –  Jernej Oct 24 '12 at 4:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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