If $G$ is $\alpha$-critical, then $G$ has no cut vertex.

Question

From Graph Theory with Applications by Bondy and Murty:

7.1.2. A graph $G$ is $\alpha$-critical if $\alpha(G-e)>\alpha(G)$ for any edge $e$ in $G$. Show that if $G$ is $\alpha$-critical, then $G$ has no cut vertex.

Here, $\alpha(G)$ is the number of vertices in a maximum independent set of $G$.

I need to show that any two edges in $G$ lie on a common cycle.

It's not hard to find that this implies that $\beta(G-e)<\beta(G)$ for any edge $e$, but I am not sure if that is useful, where $\beta(G)$ is the number of vertices in a minimal covering of $G$.

Answer 1

Suppose that there is a cut vertex $v$, and let $X, Y$ be two sets of vertices separated by $v$.

Since $G$ is $\alpha$-critical, you should be able to prove that there is a maximum independent set $I$ that contains $v$. Let $\alpha_X$ (respectively $\alpha_Y$) be the number of vertices of $X$ (respectively $Y$) included in $I$. Thus $\alpha(G) = \alpha_X + \alpha_Y + 1$.

Let $x \in X$ be a neighbor of $v$ in $X$. By removing the edge $vx$, by the $\alpha$-critical property we get an independent set $I'$ of size $I + 1$ that includes both $v$ and $x$. This is only possible if $I'$ includes $\alpha_X + 1$ vertices of $X$ (why?), and hence $X$ admits an independent set $I_X$ of size $\alpha_X + 1$. By the same argument, $Y$ admits an independent set $I_Y$ of size $\alpha_Y + 1$.

But then, $I_X \cup I_Y$ is an independent set of size $\alpha_X + \alpha_Y + 2$, which is greater than $\alpha(G)$, a contradiction.