Maximum Number of Vertices of a block-cutpoint graph

For a graph $G$ on $n \geq 1$ vertices, what is the maximum number of vertices of its block-cutpoint graph $BC(G)$?

What I have so far:

The block-cutpoint graph of a graph $G$ is the bipartite graph which consists of the set of cut-vertices of $G$ and a set of vertices which represent the blocks of $G$.

Let $G=(V,E)$ be a connected graph. Let $v$ be a vertex of $G$. Then $v$ is a cut-vertex of $G$ iff the vertex deletion $G−v$ is a vertex cut of $G$.That is, such that $G−v$ is disconnected.

A block is a maximal biconnected subgraph of a given graph $G$.

I don't really know what else I need to know to solve this.

It’s sufficient to consider connected graphs. First note that $G$ has at least $2$ non-cut vertices and therefore at most $n-2$ cut vertices. Next, let $\mathscr{B}$ be the set blocks of $G$. Let $\operatorname{bt}(G)$ be the graph whose vertex set is $\mathscr{B}$ and that has an edge $B_0B_1$ if and only if blocks $B_0$ and $B_1$ have a vertex in common.

• Show that distinct $B_0,B_1\in\mathscr{B}$ have at most one vertex in common, and that if they have one in common, it’s a cut vertex. Show further that $\operatorname{bt}(C)$ is a tree. (It’s the block tree of $G$.)

• Show that $|\mathscr{B}|\le n-1$. I used the fact that $\operatorname{bt}(G)$ is a tree to do this, which is why I introduced the block tree, but if you can find some other way to do it, that’s fine too.

It follows that $BC(G)$ has at most $2n-3$ vertices. To prove that this bound is sharp, consider the path graph with $n$ vertices.

Added: This of course applies only to the non-degenerate case $n>1$. If $n=1$, $G$ has no biconnected subgraph and no cut vertex.

• Sorry this is a late reply. Why does G have at least 2 non-cut vertices? What do you mean when you say "this bound is sharp"? Apr 24 '15 at 20:01
• @EmaLee: The link in my answer is to a proof that $G$ has at least two non-cut vertices, and that page has a further link to a page with more proofs. When we say that a bound is sharp, we mean that it cannot be improved; in this case that means that there is at least one graph on $n$ vertices whose block-cut graph has $2n-3$ vertices, so $2n-3$ cannot be replaced by any smaller function of $n$. Apr 24 '15 at 20:04
• This is false when $n=1$. Jun 3 '15 at 16:28