An $\alpha$-critical graph is a graph in which the removal of any edge increases the independence number. Sometimes isolated vertices are forbidden, but that is irrelevant for this question.

It is known that in such a graph every two adjacent edges are on a common chordless odd cycle. I am wondering about the reverse implication. Specifically:

Let $G$ be a graph in which every two adjacent edges are on a common odd chordless cycle. Prove that $G$ is $\alpha$-critical or provide a counterexample.

Btw, I expect it to be false, simply because the book would probably have hinted at an equivalence, if there was one.


1 Answer 1


I'm thinking I'm making a mistake somewhere, since I suspect this would have been the first thing anyone would have checked for a counter example: The Petersen Graph.

It can be verified that every two adjacent edges lie on a common chordless 5-cycle, yet the removal of any edge leaves the independence number at $4=\alpha (P)$. So, the Petersen Graph is not $\alpha$-critical.

If I made a mistake anywhere, someone point it out and I'll delete my answer. I do hope this works though.

  • 2
    $\begingroup$ You are absolutely right. I should have checked the Petersen graph. But I didn't. Thank you. $\endgroup$ Aug 29, 2015 at 16:57
  • $\begingroup$ Oh good. I'm glad this helped. The Petersen Graph really is amazing. $\endgroup$ Aug 29, 2015 at 16:59

You must log in to answer this question.

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