# Connected Graph Proofs

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

Try this: Let $$G$$ be a connected (simple) graph with $$n$$ vertices and $$m$$ edges. Since $$G$$ is connected, $$m\geq n-1$$, so let $$m = n-1 +k$$ for some $$k\in \mathbb{Z}_{\geq 0}$$. Recall that any connected graph contains a spanning tree $$T_0$$ as a subgraph, which necessarily has $$n-1$$ edges and 0 cycles. Let $$\{e_1, e_2, \ldots e_k \}$$ denote the set of edges not in $$T_0$$.
Now think about what happens when we add $$e_1 = (v_1,v_2)$$ into $$T_0$$. Since $$T_0$$ is a spanning tree there exists a path from $$v_1$$ to $$v_2$$ in $$T_0$$. Therefore adding $$e_1$$ to this path will produce a cycle. Let $$T_1$$ denote the subgraph consisting of $$T_0$$ with $$e_1$$.
Now think about adding in $$e_2$$. You'll see that by the same argument we will produce at least one new cycle, and the resulting graph $$T_2$$ will have at least 2 cycles. Continuing in this way we see that $$G$$ itself must contain at least $$k$$ cycles, but $$k = m -(n-1) = m-n+1$$ as desired.
For part (b), part (a) tells you that you have at least $$(m-n+1)$$ cycles. To form a spanning tree, you essentially just have to remove an edge from each of those cycles. Think about how many ways you can do that (remember a bipartite graph has no odd cycles) and you should get your answer.