MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## existence of triangle-free graphs for sparse regular graphs of degree at most n/2

Hi,

We know that for triangle-free graphs, if they are regular (i.e. same degree,d, for each vertex), then 2d <= 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 <= n, can we always find a triangle-free graph? Do you know any related results in the literature?

I'd be very glad if you could help me with it..

best,

gizem

-
 Are you asking for a triangle free $sub$-graph? – Kevin O'Bryant Dec 10 2010 at 15:16

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.