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?

Improve this question
$\endgroup$
6
  • $\begingroup$ Are you asking for a triangle free $sub$-graph? $\endgroup$
    – Kevin O'Bryant
    Commented 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
    Commented 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$
    – Sergiy Kozerenko
    Commented 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
    Commented Sep 12, 2013 at 13:18
  • $\begingroup$ Okay, I will read it. $\endgroup$
    – Sergiy Kozerenko
    Commented Sep 12, 2013 at 13:19

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Fedor Petrov
    Commented Jul 11, 2021 at 10:07
  • $\begingroup$ @FedorPetrov I rewrote the proof slightly and agree that your construction is simpler. $\endgroup$
    – Tony Huynh
    Commented Jul 11, 2021 at 12:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .