a) Prove that every graph with vertices and edges has an independent set of size .
b) Find the number of graphs with vertices and edges having no independent set of size .
a) Prove that every graph with vertices and edges has an independent set of size .
b) Find the number of graphs with vertices and edges having no independent set of size .
a) Let be a maximal independent subset of vertices and be its complement. Assume to the contrary that has at most elements and so consists of at least vertices. Since is maximal, there should be an edge from every vertex in to , so there are at least edges between and . This means that there are at most 1 edge in let's say between and . Now is an independent subset of vertices with at least elements, which is a contradiction.
b) We prove that the only answer is the union of two disjoint triangles and edges between disjoint pair of vertices. Let be a maximal independent subset of vertices, by assumption it has at most vertices and so its complement has at least vertices. Similar to the previous part, we can conclude that there are at least edges connecting vertices of to and there are at least 2 edges connecting vertices in . As the total number of edges is assumed to be , we deduce that should have exactly vertices and there are exactly 2 edges in . Also, every element of is connected to exactly one element of .
If two elements of , say and , are connected to some vertex , then must be an edge, because otherwise, form an independent set of size which is a contradiction. This observation together with the fact that there are two edges in implies that vertices in can not be connected to more than two vertices in .
Since and , there should be two vertices and two disjoint pairs in such that is adjacent to () and so are connected. Also, there is a bijection between such that the corresponding vertices are connected. This gives edges in the graph and since there are exactly edges, we conclude that the graph is the union of two triangles and disjoint edges as desired.