# How to prove that a graph does not have a block graph that is $C_n$ $n\geq 4$

The block graph of a given graph $$G$$ is the intersection graph of its blocks. Thus, it has one vertex for each block of $$G$$, and an edge between two vertices whenever the corresponding two blocks share a vertex. A biconnected component (sometimes known as a 2-connected component or block) is a maximal biconnected subgraph. The blocks are attached to each other at shared vertices called cut vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components. I know that a graph block can be a $$C_3$$ such as the graph block of a $$S_3$$ (Star graph) also know as $$K_{1,k}$$ (Complete bipartite)

• if the block graph had a cycle, the blocks that correspond to the nodes of that cycle would actually be one larger block (their intersections would not be articulation points).
– JimN
Apr 16, 2021 at 12:01
• @JimN For that to work out, we need to define something slightly different from the block graph: a graph whose vertices correspond to blocks and cut vertices, with an edge from each cut vertex to the block it's in. In this definition, a cycle might happen from having many overlapping blocks. Apr 16, 2021 at 13:38
• And actually in this definition I think the statement is not true: doesn't an $n$-edge star graph have a block graph of $K_n$, which has many long cycles? Apr 16, 2021 at 13:39
• $C_n$-free means no induced $C_n$. The only induced cycles in $K_n$ are triangles
– JimN
Apr 16, 2021 at 13:40
• Sorry, I already edited the title it wasn't that have a $C_n$ $n\geq 4$, but that it isn't a $C_n$ $n\geq 4$ Apr 22, 2021 at 0:45

Assume the block graph of $$G$$ has some cycle > 4. Choose an edge $$xy$$ in the cycle. Note that $$x$$ and $$y$$ are nodes that are connected by a path in the cycle which does not use edge $$xy$$.
So $$x$$ and $$y$$ each correspond to two blocks of $$G$$, which intersect, and their intersection should be an articulation point. Remove that vertex -- this should disconnect the graph, and in particular, disconnect a vertex in block $$x$$ from a vertex in block $$y$$. But now there is another path which connects the vertices of $$x$$ with the vertices of $$y$$ through the other path in the cycle.