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

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?

share|cite|improve this question
Are you asking for a triangle free $sub$-graph? – Kevin O'Bryant Dec 10 '10 at 15:16
@SergiyKozerenko: You are bumping an awful lot of old posts for some reason. We discussed this sort of thing here: – Todd Trimble Sep 12 '13 at 13:11
@Todd Trimble: Is it forbidden to delete obvious TeX and text mistakes and make questions more readable? – Sergiy Kozerenko Sep 12 '13 at 13:15
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. – Todd Trimble Sep 12 '13 at 13:18
Okay, I will read it. – Sergiy Kozerenko Sep 12 '13 at 13:19
up vote 10 down vote accepted

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.

share|cite|improve this answer
thanks a lot!! was very useful.. – Gizem Dec 10 '10 at 18:47

Your Answer


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.