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.