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

1. Aug 15, 2004

### 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?

2. Aug 17, 2004

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

3. Aug 18, 2004

### TenaliRaman

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.

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

Last edited: Aug 18, 2004
4. Aug 18, 2004

### e(ho0n3

Thank you for responding.

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). K4 is not bipartite so I don't understand what you want me to check.

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

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.

5. Aug 18, 2004

### 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!!

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

6. Aug 19, 2004

### e(ho0n3

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

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

As I said, I already proved the converse.

You are right. Sorry about that. Thank you.