Prove that $G$ is a block if and only if given a vertex and an edge of $G$ there exists a cycle containing them.

240 Views Asked by At

Prove that $G$ is a block if and only if given a vertex and an edge of $G$ there exists a cycle containing them.

A block of a graph $G$ is a maximal connected subgraph of G that has no cut-vertex.

Attempt:

Let $u\in V(G)$ and $a\in E(G)$, $a=wv$. By hypothesis, there exists a cycle $C$ containing $u$ and $w$. As for $v$ there are two possibilities: that it is part of the vertices of the cycle or that it is not. If $v\in V(C)$ we obtain a cycle $C'$ containing $u$ and edge $a$ as follows:

\begin{align*} C&=u, u_1, \ldots , w, w_1, \ldots v, v_1, \ldots u \\ C'&=u, u_1, \ldots , w, v, v_1, \ldots u \end{align*}

That is, we replace the part $C$ between $w$ and $v$ by the edge $a$. If $v\notin V(G)$ we have a situation equal to the previous demonstration and we can find two paths from $u$ to $v$, one of which contains edge $a$.