I'm teaching an undergraduate combinatorics class, using Harris et al.'s book ``Combinatorics and Graph Theory''. In Section 1.6 there is an exercise asking to show that for the complement of a bipartite graph, the chromatic number equals the clique number. 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, and have found other proofs online that use the K\"onig-Egerv\'ary theorem. Unfortunately, my students don't know either of these results ... they don't appear until Section 1.7 of the book.


My question is this: is there a way of showing (directly, i.e., not using Lov\'asz's perfect graph theorem) that $\chi(\overline{G})=\omega(\overline{G})$ for bipartite $G$, that avoids Hall's theorem or the K\"onig-Egerv\'ary theorem? In particular, is there a way that might be found by a student unfamilar with these results, who has only seen the basics of coloring (definition of $\chi$, greedy algorithm, Brooks' theorem, some basic bounds), and knows nothing yet about perfect graphs and the perfect graph theorem?



Proving that the complement of a bipartite graph has chromatic number equal to clique number
According to [this Wikipedia entry](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_%28graph_theory%29#Connections_with_perfect_graphs) 
the statement that $\chi(\overline{G}) = \omega(\overline{G})$ for all bipartite $G$ is actually equivalent to König's Theorem.


