Find total number of ways to disconnect the following graph

Question

Find total number of ways to disconnect the following graph:

1. $4$
2. $5$
3. $6$
4. $8$

---

My attempt:

I've done manually to find possible disconnected sets of given graph. I guess it is should be $8$.

Can you explain in formal way, please?

Answer 1

The minimum number of edges that need to be removed to disconnect the graph is $3$, and there are just $4$ ways to do this: remove all of the edges incident at one vertex of degree $3$. There are $9$ ways to remove a set $E$ of edges so that (a) the resulting graph is disconnected, and (b) removing any proper subset of $E$ leaves a connected graph. However, $5$ of these require the removal of $4$ edges, not $3$:

$$\begin{align*} &ac,bc,dc,ed\\ &ad,ac,cb,be\\ &ad,dc,ce,eb\\ &ab,bc,ce,ed\\ &ba,ac,cd,de \end{align*}$$

To verify that there really are only $4$ possibilities when you remove just $3$ edges, suppose that you remove $3$ edges, but not all $3$ of the edges incident at any of the corner vertices.

• If all three of the removed edges are incident at $c$, it’s easy to see that the resulting graph is still connected.
• If two of them are incident at $c$, removing those $2$ leaves a graph consisting of two cycles that share either one or two edges, depending on which two edges incident at $c$ were removed, and removing one more edge cannot disconnect such a graph.
• If one of them is incident at $c$, without loss of generality suppose that it’s $ac$. Then at least one of $ab$ and $ad$ was not removed; without loss of generality we may assume that $ab$ is still present. The edges $ab,cd,ce$, and $cb$ are then all present and are sufficient to connect the graph.
• If none of them is incident at $c$, the $4$ edges incident at $c$ are sufficient to connect what remains.