existence of triangle-free graphs for sparse regular graphs of degree at most n/2 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:27:15Z http://mathoverflow.net/feeds/question/48929 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/48929/existence-of-triangle-free-graphs-for-sparse-regular-graphs-of-degree-at-most-n-2 existence of triangle-free graphs for sparse regular graphs of degree at most n/2 Gizem 2010-12-10T14:47:04Z 2010-12-10T16:44:33Z <p>Hi,</p> <p>We know that for triangle-free graphs, if they are regular (i.e. same degree,d, for each vertex), then 2d &lt;= 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)</p> <p>My question is, for every graph with 2d &lt;= n, can we always find a triangle-free graph? Do you know any related results in the literature? </p> <p>I'd be very glad if you could help me with it..</p> <p>best,</p> <p>gizem</p> http://mathoverflow.net/questions/48929/existence-of-triangle-free-graphs-for-sparse-regular-graphs-of-degree-at-most-n-2/48931#48931 Answer by Tony Huynh for existence of triangle-free graphs for sparse regular graphs of degree at most n/2 Tony Huynh 2010-12-10T14:55:48Z 2010-12-10T16:44:33Z <p><strong>Yes</strong>, 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. </p> <p>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. </p>