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!


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 .

  • $\begingroup$ 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. $\endgroup$ Aug 15 '14 at 2:45
  • $\begingroup$ +1ed. Welcome to MO! I am glad you exist now. $\endgroup$
    – Tony Huynh
    Aug 15 '14 at 3:04

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.