MATH239 Study Guide - Final Guide: Bipartite Graph

• School: University of Waterloo
• Department: Mathematics
• Course: MATH239
• Professor: a

Document Summary

(cid:17) k 1 (cid:16)n 2: [3 marks] show that the number of k-subsets of {1, . Let an be the coe cient of xn in s(x). When considering the new vertices adjacent to a vertex in the tree, take them in increasing alphabetical order. 1 (b) determine if the graph in (a) is bipartite. If it is bipartite, nd a partition of the vertex set that shows it is bipartite. Prove your answer is correct in each case. 2: [5 marks] prove that every planar graph with no 3-cycles is 4-colourable, assuming that every planar graph with no 3-cycles has a vertex of degree at most 3. Show that |n (d)| |d| for all d a with |d| 10. Show the vertices of x and y in the order that they are added to these two sets during the course of the algorithm. Vertices added to x : to y : Hence give a minimum cover for the graph.