0
$\begingroup$

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?

  • 0
    I added a [proof-writing] tag since it seemed appropriate. I also fixed the TeX for you. Hope it's ok.2011-09-05

1 Answers 1

2

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$.

  • 0
    Awesome. Discrete mathematics really pounded induction proofs into my head, so I kept trying to apply the same method for this proof. Thanks again and have a great Labor Day!2011-09-05