# Proving two graphs have the same chromatic number

Let $$G= (V,E)$$ be a graph, and let $$G'= (V',E')$$ be a copy of $$G$$. That is, for each $$v ∈ V$$ there is a corresponding $$v' ∈ V'$$ and for each edge $$(u,v)∈E$$ there is a corresponding edge $$(u',v')∈E'$$. Construct a graph $$G\widehat{}$$ by drawing an edge from each $$v∈V$$ to its corresponding $$v'∈V'$$. Prove that $$\chi (G\widehat{}) =\chi (G)$$.

My work: I sketched a few graphs such that they could be colored using two color and drew $$G$$ and $$G'$$ for each. By construction it's apparent that $$G\widehat{}$$ could also be colored using two colors. But i'm having a hard time extending this to more than two colors and actually writing down a proof, as a picture doesn't really count as proof.

If I'm understanding your question correctly, the new graph $$\hat{G}$$ is just two copies of $$G$$ with the corresponding vertices connected right? If so, just think about permuting the colors on the second copy. Explicitly, say you colored $$V$$ with the colors $$\{1, 2, \ldots k\}$$. Then for $$v'\in V'$$, if the corresponding $$v\in V$$ has color $$i$$ color $$v'$$ with $$i+1 \mod k$$.
• Well you colored all the vertices in $\hat{G}$ with the same colors as $G$, so the chromatic numbers are the same. That is, if you colored $G$ with $\{ 1,2, \ldots k\}$ then the above explains how to color $\hat{G}$ with $\{ 1,2, \ldots k\}$ also. Apr 15, 2019 at 18:48
• Note that (a) $\chi (G\widehat{})$ is at least $\chi(G)$ as there is a subgraph of $G\widehat{}$ isomorphic to $G$. Yet @Edgar Jaramillo Rodriguez gave a proper coloring of $G\widehat{}$ using only $\chi(G)$ colors, this implies that (b) $\chi (G\widehat{})$ is also no more than $\chi(G)$, so (a) and (b) together imply equality.
• So $\chi(\hat{G}) \geq \chi(G)$ since every coloring of $G$ admits a coloring of $\hat{G}$ with the same number of colors. But at the same time $\chi(\hat{G}) \leq \chi(G)$ since any coloring of $\hat{G}$ contains a coloring of $G$ in its subgraph. So in fact $\chi(\hat{G}) =\chi(G)$ Apr 15, 2019 at 18:51
• I can rewrite the first sentence of my last comment: Note that (a) $\chi (G\widehat{})$ is at least $\chi(G)$, as $G$ that is a subgraph of $\chi (G\widehat{})$ is at least $\chi(G)$. But getting back to "isomorphism", the graphs $G$ and $G'$ are [by definition of "isomorphic"], isomorphic to each other.