1
$\begingroup$

To prove the statement above we solve the problems below.

Starting at any vertex $A$ in any component of $G$, assign the color red to $A$ and proceed to color vertices along simple paths from $A$, alternating between red and blue. In that way every vertex in the component is eventually reached and colored.

In the procedure described above, the color assigned to a vertex $V$ depends on the length of the path followed from $A$ to $V$. A vertex reached by a path of odd length is colored blue, while a vertex reached by a path of even length is colored red.

(a) Let $A, V$ be vertices in a graph that contains no odd cycles and suppose that there are two paths from $A$ to $V$, one of odd length and one of even length. Show that this situation is impossible by deriving a contradiction.

(b) Prove if each component of a graph is bipartite, then the entire graph is bipartite. Then show that with the vertices of some component colored as described above, no edge has the same color assigned to both of its endpoints.

My question is what are we proving by solving the problem (a)? Are we proving that no two edges share the same endpoints?

$\endgroup$
  • $\begingroup$ The proof is constructive, it tries to create blue and red edges which never touch. However how do you know this construction is well defined! Hint: you don't. So part (a) is just showing well-definedness. Once you know there will never be a point at which you have coloured both red and blue, you can continue. $\endgroup$ – mdave16 Jul 11 '17 at 23:21
  • 2
    $\begingroup$ This shows that the coloring of the vertices is well-defined, so that no vertex is being colored both red and blue. $\endgroup$ – user84413 Jul 11 '17 at 23:23
  • $\begingroup$ We are proving that two vertices can't be connected by both an odd-length path and an even-length path; i.e., if the vertices $A,V$ lie in the same component (so there are paths connecting $A$ and $V$), either all such paths are even, or else all of them are odd. $\endgroup$ – bof Jul 12 '17 at 0:03
2
$\begingroup$

In part a) we are proving that a vertex will never be coloured both blue and red. This is useful because it tells us that, in each connected component of $G$, each vertex will be assigned exactly one colour and, by construction, its neighbours will always have the "opposite" colour. So the blue vertices and the red vertices in any given component form the two "parts" of the bipartition of this component. Then, by part b), we can "collect together" the red vertices and the blue vertices in each component to form the bipartition of $G$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.