# Two-way bounding Problem 4

### Solution

$$\chi(M)=\max(\chi(P),\chi(G),2)$$

Note: most of the time, the chromatic number will be equal to $$\max(\chi(P),\chi(G))$$. Forcing $$\chi(M)$$ is only important when P and G both have chromatic number 1. That is, when neither P nor G contains any edges.

### Justification

Lower bound: P is a subgraph of M, so $$\chi(M) \ge \chi(P)$$. Similarly, $$\chi(M) \ge \chi(G)$$. We also know that $$\chi(M) \ge 2$$, because M contains at least one edge: the one connecting P to G. So $$\chi(M)\ge \max(\chi(P),\chi(G),2)$$.

Upper bound: Suppose that $$k = \max(\chi(P),\chi(G),2)$$. We can color P with k colors, because $$k \ge \chi(P)$$. Similarly, we can color G with the same k colors.

Now, suppose that x and y are the nodes connected by the new edge. If we have already assigned them different colors, then we are done.

If x and y have the same color, we must swap two of the color labels in G's coloring. That is, if x and y have color C, we find some other color D in our set. This second color D always exists because we've forced k to be at least 2. In the graph G, we then relabel each C node with D and each D node with C. Now x and y have different colors.

Now we have a coloring of M with k colors. So So $$\chi(M)\le k = \max(\chi(P),\chi(G),2)$$.