4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Moritz
    Nov 3, 2016 at 17:23

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Bonnaduck
    Nov 3, 2016 at 19:10
  • $\begingroup$ Yes it is! As I said you should be able to prove that for yourself (hey, you have to do some work as well, right?). But if you can't prove it let us know what you've tried and we can get to it. $\endgroup$ Nov 3, 2016 at 19:23

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.