# $\alpha$-critical graphs and chordless odd cycles

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

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.

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