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:
- There are no cut vertices. In this case $ b (x) = 1 $, then $b(x)-1=0$ for any $x$.
- 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$.