Suppose you have a complete graph with ten nodes (such that there is an edge between all pairs of nodes). What is the maximum independent set of this graph.
I thought the answer was $0$ but I am getting the wrong answer. My reasoning is that in a complete graph there are no independent sets of nodes. Thus the only independent set is the empty set which has size $0$.
Can anyone point me in the right direction about this? I feel as though I am making a simple mistake somewhere but cannot locate it. Have tried googling with no luck.
Best Answer
Since it is a complete graph the maximum independent set is one. Pick any node and that is the maximum independent set, because by definition of a complete graph it is connected to all other nodes.