Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a short paper I'm working on where I prove:

Theorem: Every graph on (2t-1) vertices with no (t+1)-clique has a vertex that is contained in every t-clique.

By "t-clique", I mean a complete subgraph with t vertices. It's actually a lemma for the main result in the paper, but it's where most of the work is done. It feels like something that has been done before, but I haven't come up with anything in my searches. I think it might be related to clique graphs or clique-helly graphs, but I haven't found a direct link.

Does anyone know of a paper with this result? Or another result that would imply this one? Or at least a related paper that might be worth looking into? Thanks!

share|improve this question

1 Answer 1

up vote 9 down vote accepted

Hajnal's Clique Collection Lemma implies your theorem. See Corollary 2.10 from this paper http://arxiv.org/pdf/1101.4564v5.pdf or Hajnal's original paper http://cms.math.ca/cjm/v17/cjm1965v17.0720-0724.pdf .

share|improve this answer
    
So much for that paper I was working on. But thanks -- That's exactly the sort of thing I thought might be out there, and very quick response too. –  Tyler Seacrest Aug 15 at 2:45
    
+1ed. Welcome to MO! I am glad you exist now. –  Tony Huynh Aug 15 at 3:04

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.