Graph Coloring: Proving Theorems

CS/MATH111 ASSIGNMENT 5 due Thursday, June 5 (8AM)

Individual assignment: Problems 1 and 2. Group assignment: Problems 1, 2 and 3.

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.

1

2

6

5

3

4

7

8 12 65 34 87

(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.

graph G

1

0

2

3

4

a

c

b

e

d

5 f

graph H

5

2

0

3

1

e

b

c

a

d

4

f

1

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.)

f

a

e cb

g

d

Graph G

ea

g b

f

c

d

Graph H

Submission. To submit the homework, you need to upload the pdf file into ilearn by 8AM on Tuesday, June 3, and turn-in a paper copy in class. Pictures should be imported into LATEX in pdf (see the source file to see how to do that). You can draw them in any drawing software and export in pdf, or draw by hand and scan.

2