2
$\begingroup$

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.
$\endgroup$
0

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.