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

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|improve this question
    
Are you asking for a triangle free $sub$-graph? –  Kevin O'Bryant Dec 10 '10 at 15:16
3  
@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 –  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
2  
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
show 1 more comment

1 Answer 1

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|improve this answer
    
thanks a lot!! was very useful.. –  Gizem Dec 10 '10 at 18:47
add comment

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.