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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.