# Proving that the complement of a bipartite graph is perfect

In Section 1.6 of Harris et al.'s book Combinatorics and Graph Theory, there is a question asking to show that the chromatic number equals the clique number for the complement of a bipartite graph. I assigned the problem to my students, without thinking much about the solution.

Now that I've given it some thought, I've found what seems to be a very natural proof using Hall's marriage theorem. Unfortunately, my students don't know this result ... it doesn't appear until Section 1.7 of the book!

My question is this: is there a way of showing $\chi(\overline{G})=\omega(\overline{G})$ for bipartite $G$, that avoids Hall's theorem? In particular is there a way that might be found by a student unfamilar with Hall, who has only seen the basics of coloring (definition of $\chi$, greedy algorithm, Brooks' theorem, some basic bounds)?

-
After some searching online I have found another proof, using the K\"onig-Egerv\'ary theorem; but this is also unsatisfactory since that result also appears in Section 1.7 of the book. –  David Galvin Feb 25 '12 at 3:11