Let $G$ be a connected graph with $n$ vertices and $m$ edges.
a) Prove that $G$ contains at least $m-n+1$ distinct cycles.
My attempt: Induction on $m$
Base Case: $m=n-1$: $G$ is a tree. $m-n+1=m-1-n+1=0$ which follows since a tree has 0 cycles
Inductive Hypothesis: Assume that a connected graph with $n$ vertices and $m-1$ edges has at least $m-1-n+1=m-n$ distinct edges.
Inductive Step: Suppose $G$ is connected with $n$ vertices and $m$ edges. Let $e$ be in a cycle of $G$. Then $G-e$ is connected with $m-1$ edges. By the inductive hypothesis, $G-e$ at least has $m-n$ distinct cycles. So $G$ has at least $m-n+1$ distinct cycles.
I'm not to sure about the inductive step (specifically if I can conclude with the last line)
b) Prove that if $G$ is bipartite, then $G$ contains at least $3(m-n+1)+1$ distinct spanning trees.
I'm not too sure if I have the right approach to this but I prove with induction on $m$ again, and I get stuck on the inductive step. I'm pretty sure I will have to use part a) in some way, but I can't see how. Any hints would be very helpful