0
$\begingroup$

From what I understand, a bipartite graph is a graph such that it can be divided into two disjoint sets of vertices, with each vertex in one set connecting to a vertex in the other.

I am trying to understand, but it is just not clicking. I want to see the reasoning for a simple square, since the Wikipedia article says that all cycle graphs with an even number of vertices are bipartite.

$\endgroup$
0
$\begingroup$

Think of it this way: a graph is bipartite if (and only if) you can color its vertices red and blue such that red vertices are only connected to blue vertices and vice versa. So to show that a graph is bipartite, you just need to find a coloring of the vertices that has this property.

For a square, pick one of the vertices and color it red. Then move around the square to an adjacent one and color it blue. Color the next one red, and color the last one blue. If you do this, the red vertices are only connected to the blue and vice-versa, so therefore the square is a bipartite graph.

This method will work for any cycle graph with an even number of vertices: just color them alternating red, blue, red, blue, ... as you go around. It fails if you have an odd number of vertices, since if you try to color them using this strategy, the last vertex you color will be red; and the last vertex is connected to the first vertex, which is also red. Since this results in two red vertices being connected, our coloring strategy fails.

(In fact, this argument can be refined to show that no such coloring exists for an odd-vertex cycle graph, and that therefore such a graph is not bipartite. But that's a story for another post.)

$\endgroup$
0
$\begingroup$

HINT: Look at the pairs of opposite corners . . .

$\endgroup$
1
  • $\begingroup$ Ahh, i just drew 2 pictures :) $\endgroup$ – Christopher Pagan Sep 1 '16 at 13:10

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.