In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.

The famous Nash-Williams conjecture claims that $\delta(G) \ge \frac{3}{4}n$ would be sufficient for $G$ to have a $K_3$-decomposition of its edges. (The constant is asymptotically sharp and Gustavsson's theorem answers in the affirmative with $\frac{3}{4}$ replaced by $1-10^{-24}$.)

To my untrained eye, this hypothesis on minimum degree has always seemed stronger than necessary. I am interested in weakening the hypotheses in the following direction.

If $\delta(G) > c n$ and $|E(G)|> \frac{3}{4}\binom{n}{2}$ then $G$ has a triangle decomposition.

(That is, if the minimum degree of $G$ is not too small while the average degree is at least what Nash-Williams demands, then we still have a $K_3$-decomposition.)

I can make silly counterexamples for $c \lesssim 3/28$. Just take a $K_3$-divisible but non-$K_3$-decomposable graph on $m$ vertices which is $\lesssim 3/4$-dense and disjoint union with a clique of order $6 m+1$. The resulting graph has $n=7m+1$ vertices, minimum degree about $3n/28$, and average density $\gtrsim (3/4+6^2)/7^2 = 3/4$.

Why would one want to make a hard conjecture even harder? I suppose it is just an attempt to understand what really makes it hard!

So here comes my MO question. Are there any obvious counterexamples to the above for $\frac{3}{28} < c < \frac{3}{4}$?

  • 1
    $\begingroup$ I'm not sure how I missed the following for $c = 1/2$: Take a complete graph of even order $n$ and remove a spanning disjoint union of two stars, say centered at vertices $x$ and $y$. Remove a few more edges for $K_3$-divisibility. Then (1) the average degree is near $n$; (2) the minimum degree is $n/2$ (when the two stars are balanced); and (3) edge $e = \{x,y\}$ belongs to no triangle. Can $c$ be pushed even higher than $1/2$? $\endgroup$ Jul 21, 2015 at 23:52

1 Answer 1


If you divide the vertex set into 3 parts, A, B and C, with respective sizes $an$, $bn$ and $cn$, and add all the edges except the ones connecting two vertices inside A and a vertex from A and C, then you get a graph with $\delta=bn$ and $|E|=(1-{a^2}-2ac) {n\choose 2}$. If $b<a$, you won't have a triangle-decomposition as for any 2 edges between A and B you need an edge inside B but there aren't enough. If $a=b$, then $c=1-2a$ and $|E|=(1+3{a^2}-2a) {n\choose 2}$, solving which to get $\frac 34{n\choose 2}$ edges we get that $a=\frac 12$ or $\frac 16$. As you've noted of the former in your comment, it can only give slightly less than $\frac 34{n\choose 2}$ edges, so we gotto go with $a=b=\frac 16$ and $c=\frac 23$ which gives (your) $c=\frac 16$.

I am not sure if you can also achieve $\frac 34$ with a similar example but I would not be surprised.

  • $\begingroup$ Oops, good points, I had covering the vertices with triangles in mind. But miraculously almost the same construction works for your problem! $\endgroup$
    – domotorp
    May 28, 2014 at 16:29
  • $\begingroup$ In this new construction, if you carefully count $|E|$ you will find it is less than $\frac{3}{4} \binom{n}{2}$. (I believe I have tried all of these obvious things, but I could be wrong.) I would not be surprised to see counterexamples for $c$ a little bigger than $3/28$, but I would be very surprised to see an example with "large" $c$. $\endgroup$ May 28, 2014 at 16:43
  • $\begingroup$ Thank you. This one seems to be a winner at $c=1/6$. It is actually quite similar to my example at $c=3/28$, except that the union is not a disjoint union and so you can reduce my "6". Btw, are you still claiming $3/4$ would not surprise you? It sure would surprise me! $\endgroup$ May 28, 2014 at 21:42
  • $\begingroup$ Indeed, 3/4 is farther from 1/6 than 2/3, but I still think that it might be possible to somehow blow-up a small counterexample in a clever way. $\endgroup$
    – domotorp
    May 29, 2014 at 8:36

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.