Connected Graph Proofs

Question

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

Answer 1

I think you have the right idea but trying to do it inductively might be making the problem trickier to work with.

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.