Dismiss Notice
Join Physics Forums Today!
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?

  1. Aug 15, 2004 #1
    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?
  2. jcsd
  3. Aug 17, 2004 #2
    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.

    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
    [itex]V \cap U = \varnothing[/itex].
    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.
  4. Aug 18, 2004 #3
    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 :biggrin: [/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"

    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
  5. Aug 18, 2004 #4
    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.
  6. Aug 18, 2004 #5
    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 :smile:
  7. Aug 19, 2004 #6
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook