Return to Revisions

Yes, it is always possible to find regular triangle-free graphs of any degree up to half the number of vertices. 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.