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
$\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$

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.