Sign up ×

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?

share|cite|improve this question
I added a [proof-writing] tag since it seemed appropriate. I also fixed the TeX for you. Hope it's ok. – Srivatsan Sep 5 '11 at 6:01
Thanks, Srivatsan. – raphnguyen Sep 5 '11 at 6:03

1 Answer 1

up vote 2 down vote accepted

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

share|cite|improve this answer
I couldn't figure out how to type out the complement G. You are all over this board with helpful information! So for my proof, I would write i) e is an edge of G (if and only if arrow) e is not an edge of the complement G. ii. prove this for an instance of G with clique size k? I'm not sure how graph theory proofs are expected to be written. – raphnguyen Sep 5 '11 at 6:17
Your part i) is just the definition of graph complement. The proof is really as straightforward as it sounds - don't complicate it. A clique is a cluster of vertices with all possible edges. An independent set is a cluster of vertices with no edges. So, if you have one, taking the complement gives you the other. – Austin Mohr Sep 5 '11 at 6:20
Your explanations are always crystal clear. As soon as you explain it, it clicks for me. I guess I am just more confused as to how I am expected to format the proof. Are graph theory proofs usually done in the format of discrete mathematics proofs? P(n) = ?, take an instance of P(0) to find that this statement is true, then prove P(n+1)? Or is it generally accepted to provide a proof by explanation and not equations. – raphnguyen Sep 5 '11 at 6:28
You're describing proof by induction. You'll probably find plenty of chances to use it in graph theory, but it isn't necessary here. All "proof" means is "an explanation why something is true". If you can explain it clearly without any fancy techniques like induction, then don't use them. – Austin Mohr Sep 5 '11 at 6:50
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! – raphnguyen Sep 5 '11 at 7:06

Your Answer


