4
$\begingroup$

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 half the number of vertices (complete bipartite for $2d = n$).

My question is, for all $d, n$ with $2d\leq n$, can we always find a $d$-regular triangle-free graph on $n$ vertices? Do you know any related results in the literature?

$\endgroup$
6
  • $\begingroup$ Are you asking for a triangle free $sub$-graph? $\endgroup$ Dec 10, 2010 at 15:16
  • 3
    $\begingroup$ @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 $\endgroup$
    – Todd Trimble
    Sep 12, 2013 at 13:11
  • $\begingroup$ @Todd Trimble: Is it forbidden to delete obvious TeX and text mistakes and make questions more readable? $\endgroup$ Sep 12, 2013 at 13:15
  • 2
    $\begingroup$ 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. $\endgroup$
    – Todd Trimble
    Sep 12, 2013 at 13:18
  • $\begingroup$ Okay, I will read it. $\endgroup$ Sep 12, 2013 at 13:19

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "By Hall's Theorem, $K_{n,n}$ has a perfect matching $M$" --- true, but without Hall Theorem it also has it. In what follows, Hall's theorem is more necessary, but actually we may simply join the vertex $i$ in the first part with vertices $i,i+1,\ldots,i+d-1$ in the second part (these all are residues modulo $n$) to get a $d$-regular bipartite graph with $n$ vertices in each part. $\endgroup$ Jul 11, 2021 at 10:07
  • $\begingroup$ @FedorPetrov I rewrote the proof slightly and agree that your construction is simpler. $\endgroup$
    – Tony Huynh
    Jul 11, 2021 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.