Reference no: EM13811799

Problem 1: (a) Let G = (V, E) be a graph with |V | = n, and let k be an integer, where 1 ≤ k ≤ n. Prove the following theorem: "Suppose the the vertices in V can be ordered v1, v2, ..., vn in such a way that each vertex vi has at most k neighbors among the preceding vertices v1, ..., vi-1. Then G can be colored with at most k + 1 colors." For example, the figure below shows a graph and an ordering of its vertices where each vertex has at most 3 neighbors that precede it in this ordering. So this theorem claims that this graph can be colored with 4 colors.

(b) Prove that the theorem in part (a) above implies the following statement: "If all vertices of a graph G have degree at most D then G can be colored with at most D + 1 colors". (You will cover a different proof of this theorem in the discussion. Here you only need to show how it can be derived from part (a).)

Problem 2: You are given two bipartite graphs G and H below. For each graph determine whether it has a perfect matching. Justify your answer, either by listing the edges that are in the matching or using Hall's Theorem to show that the graph does not have a perfect matching.

Problem 3: Determine which of the following two graphs are planar. Justify your answer. (You need to either show a planar embedding or use Kuratowski's theorem.)