# Independent Sets and Complements

Hi all, I am working through an exercise on independent sets. So far, I have checked these boxes to describe the image above:

• A maximum size IS in this graph is 2
• In a complement graph, node 1 must be connected to nodes 4, 5, and 6
• A clique in a graph becomes an IS in the complement graph
• If a node is in the IS then none of its adjacent nodes are in the IS

I am confused as to these two statements:

• With optimization version of the IS problem, the goal is to maximize the size of the IS
• If the size of the IS in graph G(n,m) is n, then m=0

In my class notes, I have G(V,E) where V = vertices and E = edges. If the number of vertices is n, I can't think of why the number of edges would equal zero, so I have left this unchecked. I have no idea what the optimization version is trying to imply.

-

$G(n,m)$ is shorthand for "a graph $G$ with $n$ vertices and $m$ edges". It does refer to the entire graph. However, you are given another piece of information about $G$ - it has an independent set of size $n$. That means every vertex is in the independent set. Such a graph can't possibly have any edges. –  Austin Mohr Sep 4 '11 at 6:36