Prove that the minimum number of cycles is $m-n+1$ The question I have is: 
Prove that the minimum number of cycles is $m-n+1$ in a connected graph. Where one cycle is a path that starts that begins and ends at the same vertex. Where $m$ is edges and $n$ is the vertices. 
I have no idea where to start. A few hints would be appreciated. Please do not provide me with the answer.
 A: Here is an argument that does not require any results about trees.
Suppose we start with an $n$-vertex graph that has no edges, and add $m$ edges to it, one at a time. 
When does adding an edge create a cycle? A cycle using edge $vw$ in a graph $G$ consists of following a path from $w$ to $v$ not using the edge, and then taking the edge $vw$ to return to the start. So a new cycle is created whenever there was a path already between the endpoints of the new edge.
Therefore each new edge can do one of two things:


*

*Connect two vertices that were not connected before. This reduces the number of connected components by $1$, but creates no new cycles.

*Connect two vertices that were connected before. This creates at least one more cycle.


Since we have $n$ connected components initially, option 1 can happen at most $n-1$ times, so option 2 must happen at least $m-(n-1)$ times, creating at least $m-n+1$ cycles.
This minimum value can be achieved for relatively small $n$; for example, the friendship graph has $2n+1$ vertices, $3n$ edges, and exactly $n = 3n - (2n+1) + 1$ cycles. But eventually, we get more cycles than this; for example, with $\binom n2$ edges, our only option is the complete graph, which has many more than $\binom n2 - n + 1$ cycles: it has $\binom n3$ cycles of length $3$ alone.
A: Hint: Consider a spanning tree of the graph. What happens when you add edges?
Let me first define what a tree is formally: A tree is a connected graph which contains no cycles. A leaf is a vertex of the tree which has degree $1$.
There are quite a few definitions which are equivalent, I shall choose one of the simplest and the one most suited for our application here.
Here are a few things which you will need to prove. These are not very long, if you have a proof which is very complicated then you've probably gone wrong somewhere. I've added hints in spoiler tags. Perhaps one thing I should mention. Do not let the abstract terms and definitions bog you down; a tree is exactly what you think it is (no, not the things outside). Your intuition will serve you well, you only need to take a bit of care to convert your intuition properly into a proof.
1. Every tree has at least two leaves.

Hint: Consider "walking" through the tree. Can we continue this process indefinitely? Where must we end up?

2. A tree on $n$ vertices has precisely $n-1$ edges.

Hint: Use the above fact and induction.

3. Adding any edge to a tree will create a cycle.

Hint: If you add an edge $(u,\ v)$ then can you find two different paths now from $u$ to $v$?

Now a spanning tree is a connected, cycle-less subgraph of a connected graph which contains every vertex.
4. Every connected graph has a spanning tree.

Hint: Induct on the number of edges.

These should be enough to provide a very rigorous proof of your fact.
A: If you learned what a tree is, you can do induction by $m$.
If $m=n-1$, then your graph is connected and satisfies the tree formula, so how many cycles are there.
The inductive step is easy: If you have a graph on $m+1$ edges, then $m+1>n+1$ thus your graph is not a tree, and hence must have a cycle. remove one edge from the cycle, use induction and add it back... 
A: Let $G$ be a connected graph with $n$ vertices and $m$ edges.

Claim:$\;$G has at least $m-n+1$ cycles.

Proof:

Proceed by induction on $n$.

If $n=1$, the claim holds trivially since then $m=0$ and $m-n+1=0-1+1=0$.

For $n > 1$, let $G$ be a connected graph with $n$ vertices and $m$ edges, and assume the claim holds for all connected graphs with $n-1$ vertices.

Let $c$ be the number of cycles of $G$.

Our goal is to show that $c\ge m-n+1$.

Since $G$ is connected every vertex has degree at least $1$.

Suppose some vertex, $v$ say, has degree $1$.

Then $G-v$ has $n-1$ vertices, $m-1$ edges, and $c$ cycles, hence by the inductive hypothesis, we get $c\ge (m-1)-(n-1)+1=m-n+1$, and we're done.

Next assume every vertex has degree at least $2$.

Choose vertices $u,v$ of $G$ such that the distance $d(u,v)$ is largest.

Let $w$ be a vertex of $G$ other than $v$ and let $p$ be a path of least distance in $G$ from $u$ to $w$.

Then $v$ can't be a vertex of $p$ else $d(u,w) > d(u,v)$, contrary to the choice of $u,v$.

Thus the path $p$ in $G$ from $u$ to $w$ is also a path in $G-v$.

It follows that $G-v$ is connected.

Let $k=\deg(u)$.

Then $G-v$ has $n-1$ vertices and $m-k$ edges, hence by the inductive hypothesis, $G-v$ has at least $(m-k)-(n-1)+1=m-n-(k-2)$ cycles.

Of course any cycle of $G-v$ is also a cycle of $G$.

Let $w_1,...,w_k$ be the neighbors of $v$

Since $G-v$ is connected, for each pair $w_i,w_j$ where $1\le i < j\le k$, there is a path $p_{i,j}$ in $G-v$ from $w_i$ to $w_j$. If we augment the path $p_{i,j}$ by prepending the edge $vw_i$ and appending the edge $vw_j$, we get a cycle in $G$, and these cycles are distinct from the cycles of $G-v$, and disctinct from each other.

Thus there at least ${\large{\binom{k}{2}}}$ cycles of $G$ which are not cycles of $G-v$.

Since $k\ge 2$, it follows that ${\large{\binom{k}{2}}} \ge k-1$, hence
$$
c
\ge
{\small{\binom{k}{2}}}
+
\bigl(m-n-(k-2)\bigr)
\ge
(k-1)
+
\bigl(m-n-(k-2)\bigr)
=
m-n+1
$$
as was to be shown.

This completes the proof.
