4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

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