Question

Prove that any graph with n vertices and at least n + k edges must have at least k + 1 cycles.

Answer 1

Direct proof:
   if a graph has n vertices, then it can have only at most n-1 edges with out cycles//technically a graph with n vertices and n-1 edges will be a tree, which will not have cycles
   any edge more then n-1 edges will cause one cycle
   means if you add one additional edge to n-1 edges then you will create one cycle
   if you add two additional edges to n-1 edges then you will create two cycles
   like wise
   if you add k+1 additional edges to n-1 edges then you will create k+1 cycles, means total edges will become n-1+k+1 = n+k edges
   so,any graph with n vertices and at least n + k edges must have at least k + 1 cycles
   hence proved