Question 44
a) Prove that every graph with $2n$ vertices and $n+2$ edges has an independent set of size $n$.
b) Find the number of graphs with $2n$ vertices and $n+3$ edges having no independent set of size $n$.
b) Find the number of graphs with $2n$ vertices and $n+3$ edges having no independent set of size $n$.