If $c(B)$ denotes the number of cut vertices of a simple connected
graph $G$ belonging to the block $B$; prove that the number of cut
vertices $c(G)$ of $G$ is given by $c(G)=1+\sum (c(B)-1)$; the
summation being over the blocks of $G$
I'm totally stuck in this problem. I made a few examples to maybe find a reason for this and I couldn't. My only clue about it is that maybe that -1 is to compensate overcounted vertices, because a vertex is a cut vertex iff it belogns to at least 2 blocks. But I may count a vertex a bunch of times, not only twice…And that +1, I have no idea where does it comes from, it does makes sense when $G$ is itself a block…
I'd really apreciate some hints, like useful results that I can use.
Best Answer
Denote by $cuts(B)$ the set of cut vertices contained in a block $B$.
Suppose that you can order the blocks $B_1, B_2, \ldots, B_k$ so that for any $i > 1$, exactly one vertex $v$ in $cuts(B_i)$ was in some $B_{i'}$, $i' < i$. In other words, make it so that one $v \in cuts(B_i)$ was counted previously.
If such an ordering exists, then you can say that $c(G) = c(B_1) + \sum_{i = 2}^k c(B_i) - 1$ (the minus one for the 'already counted cut vertex'). Noting that $c(B_1) = 1 + (c(B_1) - 1)$, you get your result.
What might help in establishing that ordering is that two blocks share at most one cut vertex (probably provable by contradiction).
There's a way to find this ordering using Block graphs, but it's a bit cumbersome. Essentially, it is based on the (unverified) premise that all members of a given clique share the same one and only cut vertex. But let me know if you want the details.