0
$\begingroup$

I'm trying to prove the following result:

Let $G=(V,E)$ be an undirected connected graph and $G_i=(V_i,E_i)$ be its biconnected (2-connected) components for $i=1,\ldots,k$. Prove that $a\in V$ is a cut vertex in $G$ if, and only if, $a\in V_i\cap V_j$ for some $i\neq j$.

My attempt to prove it is as follows:

$(\Rightarrow)$ Suppose $a$ is a cut vertex in $G$. Then, there exists $u,v\in V(G)-\{a\}$, with $u\neq v$, such that every path connecting $u$ and $v$ passes through $a$. We claim that $u\in V_m$ and $v\in V_n$ for some $m\neq n$. For if $u,v\in V_m$, then since $G_m$ is biconnected, $G_m - a$ is connected, so we could obtain a path in $G_m-a$ (and hence in $G_m$) connecting $u$ and $v$ that does not pass through $a$ and hence, $a$ would not be a cut vertex. Now let $P$ denote any path connecting $u$ and $v$ that passes through $a$ and let $w$ and $z$ be the adjacent vertices to $a$ in $P$. By a similar argument, $w\in V_i$ and $z\in V_j$ for some $i\neq j$. Hence, $a\in V_i\cap V_j$ as required.

$(\Leftarrow)$ Suppose $a\in V_i\cap V_j$ and $a$ is not a cut vertex in $G$. Since $G_i$ and $G_j$ are connected, we can find $u\in V_i$ and $v\in V_j$ such that $u$ and $v$ are adjacent to $a$. Let $e_i = ua$ and $e_j = av$ be the corresponding edges in $G$. Since $a$ is not a cut vertex in $G$, $G-v$ is connected, so we can obtain a path $P$ connecting $u$ and $v$ in $G$ that does not pass through $a$. But then, $C = P\cup P'$, where $P' = e_iae_j$ would be a cycle containing edges in $E_i$ and $E_j$, a contradiction, since then we would have $E_i\cap E_j \neq \varnothing$.

Is this correct? I suspect there might be something wrong with the first part of my proof, but I can't put my finger on it.

$\endgroup$

1 Answer 1

1
$\begingroup$

For part 1, seems like you are proving a claim and then just using it.

Why not just start by proving the following claim:

If $a$ is a cut-vertex, then there exist $u,v\in N(a)$ such that every $uv$-path in $G$ goes through $a$.

This should imply that $u$ and $v$ are in distinct blocks and thus $a$ belongs to both of them.

For part 2, you meant "$G-a$ is connected", no? Perhaps things will simplify if you prove the following claim first:

$|V_i\cap V_j|\leq 1$ for any $i,j$

Then you can argue that $P$ does not exist, as at least one vertex of $P$ belongs to $V_i\cap V_j$ and so does $a$.

Note that in both parts, we use the fact that both endpoints of any edge belong to the same biconnected component

Hope this helps.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .