# Proving connected graph which is not a block has specific structure

In my studies in graph theory I recently came across the following problem, but first three definitions I use:

1. A cut vertex $v$ of an undirected graph $G$ is a vertex such that $G-v$ has more connected components than $G$

2. A block is an undirected graph which is connected with no cut vertices.

3. A block of an undirected graph is a subgraph which is itself a block and not properly contained in any other block subgraph.

And here is the question on which I am stuck:

Let $G=(V,E)$ be a non-empty finite simple undirected graph which is connected and not a block, then $G$ contains at least one block with one cut vertex.

I am quite new to graph theory on this level and I have no idea how to tackle this sort of question, I have no idea and would certainly appreciate all help on this, thanks.

• What is "block with one cut vertex" supposed to mean when blocks do not have cut vrtices by definition? - Does it mean that $G$ has a cut vertex $v$ such that one of the components of $G-v$ is a block of $G$? – Hagen von Eitzen Sep 18 '16 at 19:47

Lemma. Let $n\ge 2$, let $B_1,B_2,\ldots, B_n$ be distinct blocks and $w_1,\ldots, w_n$ distinct(!) vertices such that $w_i$ is a common vertex of $B_{i-1}$ and $B_i$ for $1\le i\le n$, where we let $B_0:=B_n$. Then the union $B=B_1\cup \ldots\cup B_n$ is a block.
Proof. First note that $B$ is connected because each $B_i$ is connected and we can pass from $B_{i-1}$ to $B_{i}$ via $w_i$. In particular, we can pick a cycle $\gamma$ in $B$ that passes through $w_1,w_2,\ldots,w_n,w_1$ in that order (and possibly other vertices in-between).
Now let $v$ be any vertex of $B$. We have to show that $B-v$ is connected. Even if $v$ is among the edges of $\gamma$, $\gamma-v$ is still connected and has at least one vertex in common with each $B_i$. As $B_i-v$ is still connected, each vertex of $B_i-v$ is conencted to $\gamma-v$, and thus in total $B-v$ is connected. $\square$
Let $G$ be as in the problem statement. Define a (undirected, but not necessarily simple) graph $H$ whose vertices are the blocks of $G$ and for any two blocks of $G$, we add an edge between theses two blocks of $G$ / vertices of $H$ for each vertex these two blocks have in common in $G$. By the lemma, $H$ has no cycles, and in particular no multiple edges. As each edge of $G$ is a block and hence contained in a block of $G$, we see that $H$ is connected. Also, $H$ has at least two vertices because $G$ itself is not a block. We conclude that $H$ s a tree with at least one leaf. Then this leaf is a block of $G$ and the only edge incident with the leaf is a cut vertex of $G$ and is te only cut veretx of $G$ belonging to said block of $G$.