It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to the half of the number of vertices (complete bipartite for $2d = n$).

My question is, for every graph with $2d\leq n$, can we always find a triangle-free graph? Do you know any related results in the literature?

| cite | improve this question | | | | |
  • $\begingroup$ Are you asking for a triangle free $sub$-graph? $\endgroup$ – Kevin O'Bryant Dec 10 '10 at 15:16
  • 3
    $\begingroup$ @SergiyKozerenko: You are bumping an awful lot of old posts for some reason. We discussed this sort of thing here: meta.mathoverflow.net/questions/784/silent-edits-for-mo $\endgroup$ – Todd Trimble Sep 12 '13 at 13:11
  • $\begingroup$ @Todd Trimble: Is it forbidden to delete obvious TeX and text mistakes and make questions more readable? $\endgroup$ – Sergiy Kozerenko Sep 12 '13 at 13:15
  • 2
    $\begingroup$ Forbidden? Of course not. But I'd recommend you read that discussion anyway, just to be aware of community feelings about bumping large quantities of old posts to the front page. The general idea is moderation. $\endgroup$ – Todd Trimble Sep 12 '13 at 13:18
  • $\begingroup$ Okay, I will read it. $\endgroup$ – Sergiy Kozerenko Sep 12 '13 at 13:19

Yes, it is always possible to find regular triangle-free graphs of any degree up to half the number of vertices (as long as the number of vertices is even). To see this, first consider $K_{n,n}$. By Hall's Theorem, $K_{n,n}$ has a perfect matching $M$. Removing the edges of $M$ leaves a $(n-1)$-regular graph which is bipartite (and hence triangle-free). Repeat.

It is obviously not true if the number of vertices is odd. If $n$ and $k$ are both odd, then there are no $k$-regular graphs on $n$ vertices and hence no triangle-free ones either.

| cite | improve this answer | | | | |

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.