A Graph with Closed Paths of Even Lenght is Bipartite?

[e(ho0n3]

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 $P = (v_0, v_1, v_2, ..., v_{2n-1}, v_{2n})$ and $P' = (u_0, u_1, u_2, ..., u_{2m-1}, u_{2m})$ ($v_0 = v_{2n}$ and $u_0 = u_{2m}$) 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, $u_a,u_b \in V$. 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?

 

[e(ho0n3]

I forgot to mention a crucial detail: G is connected.

The approach mentioned in my previous post left me astray so I decided on using a different approach.

Lemma 1
All paths from v to u are all of either even or odd length.
Proof. Let P be a path from v to u of odd length and let P' be a path from v to u of even length. One can manifest a simple contradiction by considering the path P + P', which is a closed path of odd (not even) length from v to v. Hence, all paths from v to v are all of either odd or even length.

Definition
Let w be a vertex in G. Define V as the set of vertices where the path from w to a vertex in V is of even length. Define U as the set of vertices where the path from w to a vertex in U is of odd length.

Lemma 2
$V \cap U = \varnothing$.
Proof. Suppose u is a vertex in V and U. Then there is a path from w to u of even length and a path from w to u of odd length. This is not possible (Lemma 1).

Theorem 1
Every edge in G is incident on one edge in V and one edge in U.
Proof. Let (v, u) be an edge in G and suppose the path from w to v has length n. Then the path from w to u has length n + 1. If n is an even number, then n + 1 is odd, so by definition v is in V and u is in U. If n is an odd number, then n + 1 is even, so by definition v is in U and u is in V. Because the edge (v, u) is arbitrary, then every edge in G is incident on one edge in V and one edge in U.

Theorem 2
G is bipartite. Proof. This follows from Lemma 2 and Theorem 1.

I would be most content if someone could check my arguments for consistency.

 

[TenaliRaman]

Lemma 1
All paths from v to u are all of either even or odd length.
Proof. Let P be a path from v to u of odd length and let P' be a path from v to u of even length. One can manifest a simple contradiction by considering the path P + P', which is a closed path of odd (not even) length from v to v. Hence, all paths from v to v are all of either odd or even length.

u would like to check this lemma again??
(did u want to prove that all circuits are either all odd or all even?)
even then u might like to check it with K4 connected graph.

Also i am not sure but lemma1 and lemma 2 looks circular to me.

[edit]Removed a very silly comment [/edit]

Anyways there is a much easier proof of this theorem which is usually stated as,
"An undirected graph is bipartite if and only if it has no circuit of odd length"

Hint:
1>Concentrate on the iff part

2> prove that if G is bipartite then there is no circuit of odd length
2.a>Suppose the graph is coloured with black and white
2.b>assume there exits a circuit of odd length , are the number of black and white nodes on this circuit equal??
2.c>assume u define a function f(v) such that f(v) is the next vertex on the circuit after v ... is this function a bijection??
2.d> conclusion ??

3>Prove the reverse now
3.a>Given the graph has no odd circuits
3.b>Let me define a method of colouring
pick a node u and colour it black
now for every other vertex v in the component,find the shortest path from u to v
if the path length is even colour v as white else color it as black
3.c>Show that the above method is a proper 2-colouring (left as an exercise)

-- AI

 

[e(ho0n3]

Thank you for responding.

u would like to check this lemma again??
(did u want to prove that all circuits are either all odd or all even?)
even then u might like to check it with K4 connected graph.

My book never uses the word circuit. I'll assume that the words circuit and cycle (a path from v to v with no repeated edges) are synonymous. I assumed in Lemma 1 that all closed paths are of even length (this is given). K₄ is not bipartite so I don't understand what you want me to check.

Also i am not sure but lemma1 and lemma 2 looks circular to me.

I don't see any circular arguments (but who knows). Would you care to divulge?

Anyways there is a much easier proof of this theorem which is usually stated as,
"An undirected graph is bipartite if and only if it has no circuit of odd length"

This is somewhat what I need to do. I already proved the statement "If a connected graph G is bipartite, then every closed path is of even length." Now I'm trying to prove the converse. I don't know exactly what you mean by circuit though so I'm not sure that the theorem you gave me is equivalent or more specific than mine.

 

[TenaliRaman]

Yes circuit is an equivalent word for a cycle
Usually circuit is a preferred word in many literatures ... (e.g euler circuit, hamiltonian circuit etc... but it doesn't matter what we are using right now).

Sorry i really didn't understand what u were doing there in lemma 1 and now that u stated the assumption it hit me ...
So ur lemma1 and lemma2 both are correct.
GOOD JOB!

I already proved the statement "If a connected graph G is bipartite, then every closed path is of even length."

What u have actually proved is "If every closed path is of even length, then the graph is bipartite"
Note that :
p : "If every closed path is of length, then the graph is bipartite"
((Lemma1->Lemma2) & (Lemma1->Theorem1))-> p
(since lemma 1 assumes the existence of even circuits or cycles of even length, the RHS has to be p)

So u can now concentrate on the step 2 i gave to prove the converse that is if G is bipartite then all cycles are of even length

-- AI
P.S1:My theorem statement and ur statement are identical
P.S2:There is a small typo in the proof to theorem1 in the line "...then every edge in G is incident on one *edge* in V and one *edge* in U."
The starred words need to be *vertex* i believe ... just wanted to point this out in case u need to submit this proof someplace ... typos give a bad impression u know

 

[e(ho0n3]

Sorry i really didn't understand what u were doing there in lemma 1 and now that u stated the assumption it hit me ...
So ur lemma1 and lemma2 both are correct.
GOOD JOB!

Thank you. Now that I have closure, I can sleep better now.

What u have actually proved is "If every closed path is of even length, then the graph is bipartite"

Yes exactly. I already proved the converse of this statement as well (I haven't posted it though).

So u can now concentrate on the step 2 i gave to prove the converse that is if G is bipartite then all cycles are of even length

As I said, I already proved the converse.

P.S2:There is a small typo in the proof to theorem1 in the line "...then every edge in G is incident on one *edge* in V and one *edge* in U."
The starred words need to be *vertex* i believe ... just wanted to point this out in case u need to submit this proof someplace ... typos give a bad impression u know

You are right. Sorry about that. Thank you.