Problem 1 (12 pts.) Recall from Tutorial 8 that a subset of vertices S C V is an independent set in G = (V, E) if and only if Vu, ve S: {u, v} # E (that is, no two vertices in S are adjacent to each other.) Use the extended Pigeonhole Principle to show that if G = (V, E) is k-colourable then there exists an independent set in G of size at least , where n = [VI. Hint. We applied the extended Pigeonhole Principle to a graph problem in PS4. While I don't recommend you use the same pigeons and pigeonholes, you should look there to guide you in how to correctly apply the extended PHP. You might also want to look at places in lecture where we applied the (regular) PHP to graph problems, and examples from lecture and tutorial where we applied the extended PHP to non-graph problems. Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem. We give partial credit where we can. (11) Correctness. If your proof is not correct, this is where you'll get docked. You'll need to (1) define the pigeons (or set A), (1) define the pigeonholes (or set B), (1) define the function f : A + B between them, (1) briefly explain why f is well-defined, (1) correctly apply the extended PHP, (6) explain how the result of the PHP achieves the desired result of this problem. (1) Communication. We need to see a mix of notation and intuition. To get these points you must have sufficient detail to convince the reader of the result, and not so many words that things get convoluted and confusing. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you'll get docked