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

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.