Return to Answer

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.

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, by Hall's Theorem the edges of $K_{n,n}$ can be partitioned into $n$ disjoint perfect matchings. The union of $d$ of these perfect matchings is a $d$-regular bipartite graph (and hence triangle-free).

It is obviously not true if the number of vertices is odd. If $n$ and $d$ are both odd, then there are no $d$-regular graphs on $n$ vertices and hence no triangle-free ones either.

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.

Note that if $n$ and $k$ are both odd, then there are no $k$-regular graphs on $n$ vertices and hence no triangle-free ones either.

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.

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.

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.

Note that if $n$ and $k$ are both odd, then there are no $k$-regular graphs on $n$ vertices and hence no triangle-free ones either.