MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If property (P) holds for perfect graphs and almost all graphs does it hold for all graphs?

share|cite|improve this question
Perhaps I misunderstood... How about the property "G is perfect or has at least 20 vertices"? – Goldstern Sep 21 '12 at 11:31
@Goldstern: Obviously this is not the kind of property I had in mind, but you have a good point there. I was thinking of things like Hadwiger's conjecture. – Felix Goldberg Sep 21 '12 at 12:11
Take one non-perfect graph of each (large enough) order and define the property as being not equal to that chosen graph. You need to work on your question a lot before it makes sense. – Brendan McKay Sep 21 '12 at 12:53
Or then again, take any property which have a finite number of exceptions, each of them a non perfect graph. – Olivier Sep 21 '12 at 17:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.