Verifying a proof (under AC) that any (possibly non-finite) graph $G$ has a $\kappa$-coloring ($\kappa$ a cardinal) if $\chi(G)\leq \kappa\leq |V(G)|$

68 Views Asked by At

Assuming the axiom of choice it seems pretty intuitive that every simple graph $G$ has a $\kappa$-coloring if $\chi(G)\leq \kappa\leq |V(G)|$, simply color $G$ with $\chi(G)$ colors and swap out $\kappa-\chi(G)$ labels assigned to each vertex in such a manner that we never eliminate any of the original colors appearing in our labeling of $G$ (here the minus sign is denoting cardinal subtraction which is well defined because by assumption $\chi(G)\leq \kappa$). Therefore the new coloring will still have all the previous $\chi(G)$ colors as well as the $\kappa-\chi(G)$ new ones, which means the new colored graph has $\kappa$ colors, as required. Now if $G$ is finite its easy to see this works. However I'm a little concerned about the formality of my previous reasoning when moving on to non-finite graphs so I wrote it out more formally as follows:


Given any (possibly non-finite) simple graph, take any $\chi(G)$-coloring $\varphi$ now select any injection $\phi$ for which we get $\text{img}(\phi)\cap \text{img}(\varphi)=\emptyset$ and $\text{dom}(\phi)\subseteq \bigcup_{v\in V(G)}\varphi^{-1}[\{\varphi(v)\}]\setminus \{v\}$ as well as that $|\text{img}(\phi)\cup\text{img}(\varphi)|=\kappa$ so that from here we can define a function $\psi$ for any $x\in V(G)$ as follows:

$$\psi(x)=\begin{cases}\phi(x)\text{ if }x\in \text{dom}(\phi)\\\varphi(x)\text{ if }x\not\in \text{dom}(\phi)\end{cases}$$

At this point take note we have $|\text{img}(\psi)|=|\text{img}(\phi)\cup\text{img}(\varphi)|=\kappa$ and $\text{dom}(\psi)=V(G)$ further if we suppose $\{u,v\}\in E(G)$ for any $u,v\in V(G)$ then we know one of the four cases below holds:

$$(1):u\in \text{dom}(\phi)\land v\not\in \text{dom}(\phi)\implies [\phi(u)=\psi(u)\in \text{img}(\phi)]\land [\varphi(v)=\psi(v)\in \text{img}(\varphi)]\\\implies \psi(u)\neq \psi(v)\text{ because }\text{img}(\phi)\cap \text{img}(\varphi)=\emptyset$$

$$(2):u\not\in \text{dom}(\phi)\land v\in \text{dom}(\phi)\implies [\varphi(u)=\psi(u)\in \text{img}(\varphi)]\land [\phi(v)=\psi(v)\in \text{img}(\phi)]\\\implies \psi(u)\neq \psi(v)\text{ because }\text{img}(\phi)\cap \text{img}(\varphi)=\emptyset$$

$$(3):u\not\in \text{dom}(\phi)\land v\not\in \text{dom}(\phi)\implies [\phi(u)=\psi(u)]\land [\phi(v)=\psi(v)]\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\\implies \psi(u)\neq \psi(v)\text{ since }\phi\text{ is injective, thus }\{u,v\}\in E(G)\implies u\neq v\implies \phi(u)\neq \phi(v)$$

$$(4):u\in \text{dom}(\phi)\land v\in \text{dom}(\phi)\implies [\varphi(u)=\psi(u)]\land [\varphi(v)=\psi(v)]\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\\implies \psi(u)\neq \psi(v)\text{ because }\varphi(u)\neq \varphi(v)\text{ since by assumption }\varphi\text{ was a coloring of }G$$

Therefore in every case we get $\psi(u)\neq \psi(v)$ so $\forall u,v\in V(G)\left(\{u,v\}\in E(G)\implies \psi(u)\neq \psi(v)\right)$ while we also noted previously $|\text{rng}(\psi)|=\kappa$ and $\text{dom}(\psi)=V(G)$ thus $\psi$ is a $\kappa$-coloring of $G$. Proving by our explicit construction (assuming AC) that any (possibly non-finite) simple graph $G$ always has a $\kappa$-coloring, if we have that $\chi(G)\leq \kappa\leq |V(G)|$.


Now is this new refined argument I wrote above formal enough? Or did I make any assumptions I couldn't have e.g. at the start when choosing/taking arbitrary sets that satisfied certain properties.