Problem

Source: Iranian Third Round 2020 Combinatorics exam Problem1

Tags: graph theory, combinatorics, independent sets



$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