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.

  • 1
    $\begingroup$ 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$? $\endgroup$ – 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$.


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.