2
$\begingroup$

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)

2 Answers 2

1

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$.

1

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.

  • 0
    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.2012-10-24