Clique and Independent Set Proof I am currently working on an exercise that is described like so: > Prove that a graph $G$ has a clique of size $k$ if and only if $\overline{G}$ has an independent set of size $k$, where $\overline{G}$ is the complement of $G$. (Note for if and only if proofs: if you wish to prove a statement of the form "A if and only if B", then you must prove "if A then B" and "if B then A"). Proofs are not my strong point and the class notes on this section is very vague. I'm not sure how to go about beginning this proof. I can't visually imagine in my head how proving one graph with a clique size equal to its complement's independent set would provide proof for all future graphs. Can someone please break this down in layman's terms for the thoroughly confused?

By definition, $e$ is an edge of $G$ if and only if $e$ is not an edge in $\overline{G}$ (this is a more standard notation for complement). If you have a clique of size $k$ in $G$, then you have $k$ vertices where every possible edge between them is included. Thus, in $\overline{G}$, _none_ of these edges are present, and therefore these $k$ vertices form an independent set of size $k$. Similarly, if you start with an independent set in $\overline{G}$, there is a corresponding clique in $G$.