1. Let $$G$$ be a simple undirected graph, and let $$H$$ be constructed from $$G$$ by adding a vertex $$v^*$$ with edges between $$v^*$$ and $$k$$ vertices in $$G$$. Prove that if $$k < \chi(G)$$ then $$\chi(H) = \chi(G)$$.

2. Give an example to show that the converse is not true.

---

### Proof of the statement

If $$k < \chi(G)$$ then $$\chi(H) = \chi(G)$$.

#### Scratchwork

Chromatic number: $$\chi(G)$$ is the smallest number of colors we can use to give a coloring of $$G$$. This means (1) We can color $$G$$ using $$\chi(G)$$ colors, and (2) If there is a coloring of $$G$$ with $$\ell$$ colors, then $$\chi(G) \le \ell$$.

If we can show that $$\chi(G) \le \chi(H)$$ and $$\chi(H) \le \chi(G)$$, then $$\chi(G) = \chi(H)$$.

$$\chi(G) \le \chi(H)$$: let $$c$$ be coloring of $$H$$ with $$\chi(H)$$ colors. Deleting $$v^*$$ and its incident edges recovers $$G$$, and then $$c$$ describes a coloring of $$G$$ with $$\chi(H)$$ colors.

For the other direction, let $$c'$$ be a coloring of $$G$$ with $$\chi(G)$$ colors. Then maybe somehow we can color the vertices of $$H$$ as follows: if $$v$$ was a vertex of $$G$$, then give it the color $$c'(v)$$, and then find a color for $$v^*$$ that's already one of the colors used by $$c'$$.

#### Proof

Let $$G$$, $$H$$ be graphs as described in the problem statement. 

$$\chi(G) \le \chi(H)$$: let $$c$$ be coloring of $$H$$ with $$\chi(H)$$ colors. Deleting $$v^*$$ and its incident edges recovers $$G$$, and then $$c$$ describes a coloring of $$G$$ with $$\chi(H)$$ colors.

$$\chi(H) \le \chi(G)$$: let $$c'$$ be a coloring of $$G$$ with $$\chi(G)$$ colors. We will describe a coloring $$c_H$$ of $$H$$ with $$\chi(G)$$ colors. For $$v \in V(G)$$, $$c_H(v) = c'(v)$$. For each neighbor $$u$$ of $$v^*$$ in $$H$$, $$c_H(v^*)$$ cannot equal $$c_H(u) = c'(u)$$. Since there $$k$$ neighbors of $$v^*$$, this leads to at most $$k$$ colors that $$v^*$$ cannot be. Since $$k < \chi(G)$$, there's some color not used by the neighbors of $$v^*$$ in $$c'$$. So we can set $$c_H(v^*)$$ to this leftover color. Thus $$c_H$$ describes a coloring of $$H$$ with $$\chi(G)$$ colors.

So $$\chi(G) = \chi(H)$$.

---
---
---

### Counterexample for the converse

Converse: If $$\chi(H) = \chi(G)$$ then $$k < \chi(G)$$.

Need to find $$G$$, $$H$$ matching the problem description so that $$\chi(G) = \chi(H)$$, but $$k \ge \chi(G)$$.

#### Ideas

What do we know the chromatic numbers of?

* $$\chi(K_n) = n$$
* $$\chi(C_n) = \begin{cases} 2 & \text{if $n$ is even} \\ 3 & \text{if $n$ is odd} \end{cases}$$
* $$\chi(L_n) = 2$$

We can't use $$K_n$$ for $$G$$ because if $$k \ge n$$, then $$H = K_{n+1}$$.

**PrairieLearn does not support tikz!**

$$G = L_2$$:

$$\begin{tikzpicture}
\node (1) at (0,0) {1};
\node (2) at (1,0) {2};
\draw (1) -- (2);
\end{tikzpicture}$$

$$H$$:

$$\begin{tikzpicture}
\node (1) at (0,0) {1};
\node (2) at (2,0) {2};
\node (v) at (1,1) {$v^*$};
\draw (1) -- (2) -- (v) -- (1);
\end{tikzpicture}$$

$$\chi(G) = 2$$, $$\chi(H) = 3$$

#### Counterexample

$$G = L_3$$:

$$\begin{tikzpicture}
\node (1) at (0,0) {1};
\node (2) at (1,0) {2};
\node (3) at (2,0) {3};
\draw (1) -- (2) -- (3);
\end{tikzpicture}$$

$$H$$:

$$\begin{tikzpicture}
\node (1) at (0,0) {1};
\node (2) at (1,0) {2};
\node (3) at (2,0) {3};
\node (v) at (1,1) {$v^*$};
\draw (1) -- (2) -- (3) -- (v) -- (1);
\end{tikzpicture}$$

$$\chi(G) = 2$$, $$\chi(H) = 2$$, $$k = 2$$.

This is a valid counterexample.

---
---
---
---
---
---
---