Let $G$ be a triangle-free graph with $t^2$ vertices. Prove that $G$ contains a set of $t$ vertices that form an independent set. I don't know how to start this proof. Please help.

Observation: If $G$ has a vertex $v$ of degree at least $t$, then the neighbors of $v$ form an independent set of size $t$, since an edge within the neighborhood will create a triangle. So, then if it is not the case, every vertex has degree at most $t-1$. How do we construct an independent set?

  • 2
    $\begingroup$ Suppose your graph has $n$ vertices, and suppose each vertex has degree at most $t-1.$ Let $S$ be a maximal independent set, of size $s.$ Can you show that $n\le st?$ $\endgroup$ – bof Aug 16 '17 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.