# Let $G$ a connected graph, and $B(G)$ the set of blocks of $G$, $cv(G)$ the set of cut vertex of $G$

Let $$G$$ a connected graph, and $$B(G)$$ the set of blocks of $$G$$, $$cv(G)$$ the set of cut vertex of $$G$$, $$b(x)$$ the number of blocks that contain $$x$$. Show that $$|B(G)|=1+\sum_{x\in V(G)}(b(x)-1)$$

getting the result.

One way was, consider two cases:

1. There are no cut vertices. In this case $$b (x) = 1$$, then $$b(x)-1=0$$ for any $$x$$.
2. There are cut vertices. In this case $$x$$ is in at least $$2$$ blocks, so $$b(x)\ge2$$, therefore $$b(x)-1\ge1$$. Then we can take the sum.

There may be a simpler counting argument, but you can do induction on the number of blocks of $$G$$. The base case of $$1$$ block is simple enough.

Note you will need the fact that if $$G$$ has a cut-vertex, then there is a block $$H$$ of $$G$$ containing exactly one cut-vertex, $$x$$. I believe one can see this fairly quickly by contradiction.

We then remove the vertices of $$H - x$$ from $$G$$ to obtain $$G'$$, a graph with $$1$$ fewer block than $$G$$. Then $$G'$$ satisfies the induction hypothesis. We have \begin{align} |B(G)| &= |B(G')| + 1\\ &= \left(1 + \sum_{v \in V(G')} (b(v) - 1)\right) + 1\\ &= 1 + \sum_{v \in V(G)} (b(v) - 1). \end{align} The final equality comes from the fact that $$b(x)$$ in $$G$$ is one more than it is in $$G'$$, and for all other vertices $$w$$ in $$H$$ (the vertices we removed) we have $$b(w) = 1$$ in $$G$$, i.e. $$b(w) - 1 = 0$$.