# Two-way-bounding study problems

### Problem 1

What is the chromatic number of the following graph? Justify your answer.

### Problem 2

(Do problem 1 and check your solution before attempting this problem.)

What is the chromatic number of the following graph? Justify your answer.

### Problem 3

Let's define sets A and B as follows:

• $$A = \{(x,y) \in \mathbb{R}^2 : y = 3x + 7\}$$
• $$B = \{\lambda(-2,1) + (1-\lambda)(1,10) : \lambda \in \mathbb{R}\}$$

Prove that A=B.

Hint: this is in the two-way bounding section. What technique do you think we want you to use?

### Problem 4

Recall that if G is a graph, then $$\chi(G)$$ is its chromatic number. Suppose that P is a connected graph and G is another connected graph, not connected to P. Now, create a new graph M which consists of a copy of P, a copy of G, and a new edge that connects some vertex of P to some vertex of G. For example, suppose that P is $$C_5$$ and G is $$K_4$$. Then M might look as follows, where g marks vertices of G and p marks vertices of P, and the new edge is the dashed line.

Give a formula expressing $$\chi(M)$$ in terms of $$\chi(P)$$ and $$\chi(G)$$? Be as precise as possible and justify your answer.