If I were to have a graph (without loops and parallel edges) having 10 vertices and 20 edges, what could be maximal possible size of an independent set?
I've tried constructing a graph and checking and the maximum I've gotten is 5. I was wondering if I'm missing something and there could be 6, and if there's any method I could use to prove that it would always be 5 or 6. Any help would be appreciated and thank you in advance!
Best Answer
Hints.
The complete bipartite graph $K_{7,3}$ has 21 edges and its independence number is $7$.
The independence number of a graph with ten vertices and 20 edges cannot be greater than 7. This is easy to check.