Graph Theory 6: Two-Colorable Graphs (Proof)

The stage was set last time for the proof of the following statement.
A graph is 2-colorable if and only if it contains no odd cycles.

An if and only if statement means that the two statements imply each other, so to prove this we have to prove both directions. This amounts to proving two statements.
The first is that if a graph is two colorable, then it contains no odd cycles.

We will prove it using contradiction, so we assume that it DOES contain an odd cycle and show this leads to a contradiction.
Since the graph is two colorable, we can say that every vertex is one of two colors, red or blue. No red vertex is adjacent to any other red vertex and no blue vertex is adjacent to any other blue vertex.
Choose any arbitrary vertex on the graph, call it V. Without a loss of generality we can suppose that this vertex is red.

If we start a path from this vertex, not repeating any edges then as we go from vertex to vertex we can alternate colors because the graph is two-colorable. Starting from V and going along one edge sends you to a blue vertex, then a red one, then a blue one, alternating colors at each vertex. Because of this, going along an odd number of edges lands you on a blue vertex, while going along an even number of vertices lands you on a red vertex.

Applying this idea we can see what happens if we have an odd cycle. Starting at a red vertex, if we go around an odd number of edges we have to land at a blue vertex, but if we go around an odd number of edges back to where we started then we get a red vertex. A vertex cannot be both red and blue so this is a contradiction, therefore it is impossible to have an odd cycle in a graph which is 2 colorable.

So we have proved the following. If a graph is two colorable then it contains no odd cycles.

Now we want the same thing backwards, a graph with no odd cycles is two colorable. This turns out to be harder and needs some other proofs first.

Unfortunately/fortunately I was given a TA position for next quarter out of nowhere. I will be teaching complex analysis and discrete math. Both courses will take a considerable amount more effort than teaching pre-calculus if I still want to be a semi-decent teacher, so I will probably put Graph Theory on hold and start talking about those two subjects as I go through the quarter. Hopefully this will help me teach it better.

Advertisements
This entry was posted in Graph Theory and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s