The title says it all. I'm having trouble showing:(adsbygoogle = window.adsbygoogle || []).push({});

If G is a graphs where all the closed paths in G are of even length, then G is bipartite.

G is bipartite if I can find 2 vertex sets V and U such that every edge is of the form (v,u), v in V and u in U. I was thinking of the following:

Suppose [itex]P = (v_0, v_1, v_2, ..., v_{2n-1}, v_{2n})[/itex] and [itex]P' = (u_0, u_1, u_2, ..., u_{2m-1}, u_{2m})[/itex] ([itex]v_0 = v_{2n}[/itex] and [itex]u_0 = u_{2m}[/itex]) are closed paths of even length.

If these paths don't share any vertices, then I can group all even-indexed vertices in V (for example) and the rest (odd-indexed vertices) in U. If both paths share one vertex, I can do the same (I just have to make sure that the shared vertex is in only one of V or U). If the paths share two vertices, then problems arise.

Say I decided to group all even-indexed vertices of path P into V and the rest into U. Now suppose that for two vertices in P' with even index a and odd index b respectively, [itex]u_a,u_b \in V[/itex]. I want to prove this situation as impossible but I haven't had any luck doing so. Maybe my approach is completely wrong but I just don't see what else to do. Maybe somebody can shed some light on this?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# A Graph with Closed Paths of Even Lenght is Bipartite?

**Physics Forums | Science Articles, Homework Help, Discussion**