&(2)G does not contain any odd simple circuit, we prove G is bipartite Since a graph is bipartite iff each component of it is, we may assume that G is connected Pick a vertex uE Vand put V=xl(u, x) is even simple path, ,and v2=yl(u, y is odd simple pathy oo 1)We prove v(G=ViUV2, Vinv2=D Letv∈v1nV2 there is an odd simple circuit in G such that these edges of the simple circuit cp, U p2 s each edge joins a vertex of v to a vertex of va❖ (2)G does not contain any odd simple circuit, we prove G is bipartite ❖ Since a graph is bipartite iff each component of it is, we may assume that G is connected. ❖ Pick a vertex uV,and put V1={x|l(u,x) is even simple path} ,and V2={y|l(u,y) is odd simple path} ❖ 1)We prove V(G)=V1∪V2 , V1∩V2 = ❖ Let vV1∩V2 , ❖ there is an odd simple circuit in G such that these edges of the simple circuit p1∪p2 ❖ each edge joins a vertex of V1 to a vertex of V2