# Counting the number of graphs with a certain property

How many simple graphs exist with the property that such a graph $G$ has chromatic number 3, but given any edge $e$ in $G$, $G - e$ has chromatic number 2?

Is there some sort of standard criteria to automatically make such a simple graph follow this behaviour? (i.e. an "easy" way to tell, given any graph $G$?)

-

I found something in the text that says if a graph has an odd cycle, then $\chi (G) \geq 3$. But how do I check all simple graphs with odd cycles to see which follow the property above? – user41419 Apr 10 '13 at 2:34
If you remove all the edges but those of the odd cycle the chromatic number will still be greater or equal than $3$... – Quimey Apr 10 '13 at 2:35
Each odd cycle has chromatic number $3$. Remove any edge and the cycle turns into a path with chromatic number $2$. There are infinitely many odd length cycles $\dots$ – Michael Biro Apr 10 '13 at 4:08