sketch:1)Take the biggest independent set of the graph and let its edge set be $A$ and let the remaining vertices be in a set $B$.It is clear that every vertex in $B$ has at least one neighbor in $A$.So $B$ has at most $n+2$ vertices.Now assume that $B$ has exactly $n+2$ vertices then every vertex in $B$ has exactly $1$ vertex in $A$ and there are no edges inside $B$.Now notice that there is a vertex in $A$ that has at least two neighbors in $B$ now swaping its neighbors with the vertex in $A$ will give a contradiction.Similarly you can disprove that $B$ can't have $n+1$ vertices. 2)Using the same technic as the previous part it is easy to see that the answer is two triangles and bare edges.

For part 1, we use induction on $n$. For the base case $n=2$ we have $4$ edges and $4$ vertices, since $4<\binom{4}{2}$, we are done. If the case $n=k$ is true, to argue for the case $n=k+1$, we add $2$ vertices (say $A$ and $B$) and $1$ edge, then at most one of $A$ and $B$ (say $A$) is connected with a vertex of that independent set $S_k$ of size $k$ (since there are just $1$ new edge), for this case $n=k+1$ we can thus take the independent set $S_{k+1}$ to be $S_k\cup \{B\}$, this obviously satisfy the condition. Done.

Can anyone post a solution for part 2?

Part 1: Let $G=(V,E)$ be the orginal graph in the problem. Take $G'$ be the complement of $G$. Then we have to show to there is at least $1$ $K_n$ in $G'$ Since $|V(G)|=n+2$ then $$ |V(G')| = { 2n \choose n} - n-2 = n(2n-1)-n-2=2(n^2-n-1) $$ From Mantel-Turan Theorem, we have to show that $$ 2(n^2-n-1) > \lfloor \frac{1}{2} \cdot \frac{n-2}{n-1} \cdot (2n)^2 \rfloor $$Which is true because $$ 2(n^2-n-1) > \frac{1}{2} \cdot \frac{n-2}{n-1} \cdot (2n)^2 \Leftrightarrow n^3-2n^2+1 > n^3-2n^2 \text{ (Always True)} $$ Part 2: With the same idea of applying the Mantel-Turan Theorem, the graphs that follow by the condition 2 must have the complement $G'$ that satisfies the Turan Condition: $$ 2n^2-2n-3 \le \lfloor \frac{1}{2} \cdot \frac{n-2}{n-1} \cdot (2n)^2 \rfloor =2n^2-2n-2 + \lfloor \frac{-2}{n-1} \rfloor $$Which is equivalent to $$ \lfloor \frac{-2}{n-1} \rfloor \ge -1 $$But since for $n \ge 3$, the equality holds, means $G'$ (The complement of the original graph) must be the Turán graph Then the number of graphs in the original problem is the number of way to paritite the set of $2n$ elements into $2$ set of $3$ elements and $n-3$ sets of $2$ elements, which is $$ \frac{(2n)!}{9 \cdot 2^{n-3} \cdot (n-3)! \cdot 2! } $$

nbdaaa wrote: [ Part 2: With the same idea of applying the Mantel-Turan Theorem, the graphs that follow by the condition 2 must have the complement $G'$ that satisfies the Turan Condition: $$ 2n^2-2n-3 \le \lfloor \frac{1}{2} \cdot \frac{n-2}{n-1} \cdot (2n)^2 \rfloor =2n^2-2n-2 + \lfloor \frac{-2}{n-1} \rfloor $$Which is equivalent to $$ \lfloor \frac{-2}{n-1} \rfloor \ge -1 $$But since for $n \ge 3$, the equality holds, means $G'$ (The complement of the original graph) must be the Turán graph Then the number of graphs in the original problem is the number of way to paritite the set of $2n$ elements into $2$ set of $3$ elements and $n-3$ sets of $2$ elements, which is $$ \frac{(2n)!}{9 \cdot 2^{n-3} \cdot (n-3)! \cdot 2! } $$ For part B the answer is one, the graph being two triangles and $n-3$ edges between $n-3$ disjoint pair of vertices

overly complex solution At first, I proved it the same way as @nbdaaa. However, I got uneasy when I saw @AgentC's post, so I thought, I might have made a mistake and tried to prove AgentC's result. The solution below is hence kinda weird.

Remark: Not sure who made the mistake, by I got $(3!)^2$ in the denominator, not $9$. (I am tired right now, so there could be quite a few mistakes, let me know if you find any)

Mr.C wrote: $1)$. Prove a graph with $2n$ vertices and $n+2$ edges has an independent set of size $n$ (there are $n$ vertices such that no two of them are adjacent ). $2)$.Find the number of graphs with $2n$ vertices and $n+3$ edges , such that among any $n$ vertices there is an edge connecting two of them Part 1 : Prove by induction : Base: n=2 notice K_4 has 6 edges but we have 4 edges thus there is vertexes like A and B such as edge AB don't exist therefore it's enough to choose A and B Induction hypothesis: statement is true for any n less than k it's enough to prove the statement is true for k Induction step: define (a) such as (a) has minimum degree by pigeonhole principle we now d(a)<2 there are 2 cases Case 1: d(a)=0 now we define (b) such as (b) has maximum degree now ignore (a),(b) and every edges of (b) now we use induction hypothesis and add (a) to independent set Case 2: d(a)=1 now we define (b) such as (b) is the neighbor of (a) now ignore (a),(b) and every edges of (b) now we use induction hypothesis and add (a) to independent set

Mr.C wrote: $1)$. Prove a graph with $2n$ vertices and $n+2$ edges has an independent set of size $n$ (there are $n$ vertices such that no two of them are adjacent ). $2)$.Find the number of graphs with $2n$ vertices and $n+3$ edges , such that among any $n$ vertices there is an edge connecting two of them Part 2 : Claim 1 : there is no graph for n=2 Prove: notice K_2=6 and we have 5 edges thus there are vertexes A and B such as we don't have edge AB therefore it's enough to choose A and B in independent set Claim 2 : there is only 1 graph for n>2 Prove: we first prove there is at least 1 graph for any n>2 Construction : we create 2 triangles and pair other vertexes one by on and we construct edge of any pair Uniqueness : Prove by induction: Base: if n=3 and we have any vertex with degree 1 then by part 1 and claim 1 then graph has atleast 1independent set of size n which is contradiction therefore every vertex have degree of 2 thus graph is p_6 or 2 triangles if graph is 2 triangles claim is proved and if graph is p_6 we just choose odd placed vertex which is contradiction Induction hypothesis : graph is unique for every n less then k it's enough to prove statement for n=k Induction step: we define (a) such as (a) has minimum degree there are 2 cases Case 1: d(a)=0 now consider (b) such as (b) have maximum degree now by part 1 it's enough to ignore (a), and (b) and every edges of (b) and add (a) to independent set which makes k sized set independent set which is contradiction Case 2 : d(a)=1 define (b) such as (b) is neighbor of (a) if (b) has no neighbor then by induction hypothesis claim is true if (b) has neighbor such as (c) , then we will ignore (a),(b) and every edge of (b) then use part 1 and add (a) to independent set which is contradiction

Autistic_Turk wrote: Mr.C wrote: $1)$. Prove a graph with $2n$ vertices and $n+2$ edges has an independent set of size $n$ (there are $n$ vertices such that no two of them are adjacent ). $2)$.Find the number of graphs with $2n$ vertices and $n+3$ edges , such that among any $n$ vertices there is an edge connecting two of them Part 2 : Claim 1 : there is no graph for n=2 Prove: notice K_2=6 and we have 5 edges thus there are vertexes A and B such as we don't have edge AB therefore it's enough to choose A and B in independent set Claim 2 : there is only 1 graph for n>2 Prove: we first prove there is at least 1 graph for any n>2 Construction : we create 2 triangles and pair other vertexes one by on and we construct edge of any pair Uniqueness : Prove by induction: Base: if n=3 and we have any vertex with degree 1 then by part 1 and claim 1 then graph has atleast 1independent set of size n which is contradiction therefore every vertex have degree of 2 thus graph is p_6 or 2 triangles if graph is 2 triangles claim is proved and if graph is p_6 we just choose odd placed vertex which is contradiction Induction hypothesis : graph is unique for every n less then k it's enough to prove statement for n=k Induction step: we define (a) such as (a) has minimum degree there are 2 cases Case 1: d(a)=0 now consider (b) such as (b) have maximum degree now by part 1 it's enough to ignore (a), and (b) and every edges of (b) and add (a) to independent set which makes k sized set independent set which is contradiction Case 2 : d(a)=1 define (b) such as (b) is neighbor of (a) if (b) has no neighbor then by induction hypothesis claim is true if (b) has neighbor such as (c) , then we will ignore (a),(b) and every edge of (b) then use part 1 and add (a) to independent set which is contradiction diagram for construction