- #1
e(ho0n3
- 1,357
- 0
The title says it all. I'm having trouble showing:
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?
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?