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

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

• If a simple conneted graph on more than $3$ vertices does not have a cut vertex, it does not have a bridge. If such a graph does not have a bridge, it is $2$-edge-connected. In a $2$-edge-connected graph every two distinct edges lie on a common cycle. Nov 3, 2016 at 17:23

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.
• Why must $v$ be in $I$? Is it the case that for any vertex in an $\alpha$-critical graph, there exists a maximum independent set containing that vertex? Nov 3, 2016 at 19:10