The block graph of a graph $G$ is a bipartite graph $H$ in which one partite set
consists of the cut-vertices of $G$, and the other has a vertex $b_i$ for each block $B_i$ of $G$. We include $(v , b_i)$ as an edge of $H$ if and only if $v$ $in$ $B_i$.
Attempt: Proof by Contradiction
Suppose it is not the case that the block graph is a tree. In that scenario either the graph contains cycle or it is disconnected. From the above definition of a block graph, it is not possible to create a cycle since an edge can only exist between the two partite sets. Thus we need to show that the graph is not disconnected. If the graph is disconnected, there exists a cut vertex which does not belong to any block.
I got stuck after this point. How do I complete the proof?
Best Answer
It looks like you are on the right track, but we need to be careful. I don’t think what you have there shows that the block graph is acyclic.
To see that the block graph is acyclic, we can note that if there was a cycle, $C$, in the block graph, this cycle would necessarily correspond to at least one cycle, $C’$, in the original graph. Every vertex in $C’$ must all belong to the same block, say $B_1$. This implies that $C$ can only pass through one vertex, $b_1$, from the partite set corresponding to block vertices. Since the block graph is bipartite, this is a contradiction. Thus our block graph is acyclic.
Now, we can show connectivity directly. Given two vertices $u$ and $v$ in our block graph, we can find a path from one to the other. We can break into cases based on which partite sets these vertices are from. Here I will only show how to find a path if both vertices are block vertices. The cases where both vertices are cut vertices, or one vertex is a block vertex and one is a cut vertex follow similarly. (let me know if you can’t figure them out, and I will add more detail.)
Assume $u$ and $v$ are block vertices, and let $B_1$ and $B_2$ be the blocks corresponding to $u$ and $v$ respectively. Let $x\in B_1$ and $y\in B_2$ be vertices in the original graph. Since the original graph is connected, there is some path $P$ between $x$ and $y$. This path corresponds to a path $P’$ between $u$ and $v$ in the block graph. Indeed, $P$ must go through some number of blocks, passing from one to the next through a cut vertex contained in both blocks. This gives us the path in the block graph.
Thus the block graph is connected and acyclic, so it is a tree.