# Two-way bounding Problem 4

### Partial Solution

To a first approximation \(\chi(M)\) is the larger of
\(\chi(P)\) and \(\chi(G)\).

You might have thought that you need one more color, to deal with the
possibility that the connector edge joins two nodes with the
same color. If so, take a concrete example graph illustrating
this situation and think about how you might modify the coloring
to remove the problem. Remember that the color names are arbitrary.
So if you give me a coloring with blue, red, and yellow, it's basically
the same coloring if I change all the blue nodes to green.

For this problem, you should be able to get an exact answer, not just
an upper or lower bound.

If you are having trouble writing
"the larger of \(\chi(P)\) and \(\chi(G)\)" as a formula without
breaking into cases, try using the max function.
An answer with cases isn't wrong, but it's less elegant since there
is a good alternative. Also, you'll end up using the max function
a lot in engineering applications.

When you think you have a method that works for typical graphs,
see if it needs to be modified to handle any special cases.
Think about graphs that are extreme on some property, e.g.
very small, many edges (e.g. complete graphs),
few edges (e.g. no edges).

In your justification, did you
argue both the upper and lower bounds?
The upper bound can be based on your method for coloring
the combinated graph.
The lower bound argument will need to explain why it
can't be done with fewer colors.

When you've fixed the above issues, look at the
full solution.