Possible numbers of cycles in a connected graph $H$ when $e(H) = |H| + 1$

22 Views Asked by At

Let $H$ be a connected graph such that $e(H) = |H| + 1$. How many cycles may $H$ have?

I can only show that this number is at least $2$ (by more generally showing, e.g. by induction, that if $e(H) = |H| + s$ for any $s\geq - 1$, then $H$ has at least $s+1$ cycles; I can also show that for $s=0, -1$ there are exactly $s+1$ cycles).

Any help appreciated!

1

There are 1 best solutions below

0
On BEST ANSWER

Hint Pick $T$ to be a spanning tree for $H$. Then $$e(T)=|T|-1=|H|-1=e(H)-2$$

Therefore, $H$ is a spanning tree with two extra edges.

Now, think what hapens when you add the two edges. The first edge creates a cycle. When you add the second edge, you create how many new cycles?