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.
Best Answer
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.