Is the clique cover number of a graph always greater or equal than the maximum independent sets? I'm trying to prove the above and I came up with the following:
Given graph $G=(V, E)$.
Let $C_{\min}$ be the minimum set that contains the cliques which cover the graph $G$.
Let $U_{\max}$ be a maximum independent set.
Assuming $|U_{\max}| > |C_{\min}|$:
We then have
$\exists v_i, v_j \in U_{\max}: v_i, v_j \in C_i$, $C_i \in C_{\min}$
this implies that $v_i$ and $v_j$ are adjacent which then implies $v_i, v_j \notin U_{\max}$
which is a contradiction.
Therefore $|U_{\max}| \leq |C_{\min}|$
Now this looks plausible to me but I am a little unsure of wether this line of argument is correct or not
 A: Let $G=(V,E)$ be a graph and $\overline G=(V,\binom{V}{2}\setminus E)$ the complement, where $\binom{V}{2}=\{e\subseteq V:|e|=2\}$ are all edges on $V$. Let $c(G)$ denote the minimum clique cover number, $\chi(G)$ the chromatic number (the least number of colors required for a proper coloring), $\alpha(G)$ the independence number and $\omega(G)$ the clique number (maximum size of a clique). Notice that $c(G)=\chi(\overline G)$ because for a minimum clique cover we assign one color to each clique, which yields a proper coloring of $\overline G$ (since there the vertices in any specific clique in $G$ are not adjacent in $\overline G$), yielding $\chi(\overline G)\le c(G)$. Conversely, for a proper coloring of $\overline G$ with $\chi(\overline G)$ colors, notice that there is no edge between vertices of the same color and thus each color class is a clique in $G$. This shows that $c(G)\le\chi(\overline G)$, and thereby $c(G)=\chi(\overline G)$.
Similarly, an independent set of size $\alpha(G)$ is a clique in $\overline G$, so $\alpha(G)\le\omega(\overline G)$. Conversely, each clique in $\overline G$ is an independent set in $G$, so $\alpha(G)=\omega(\overline G)$.
So, it's sufficient to show that $\omega(G)\le\chi(G)$, but we clearly need $n$ colors for a proper coloring of a clique of size $n$. This shows that $\alpha(G)=\omega(\overline G)\le\chi(\overline G)=c(G)$.
