# Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

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}$?

• 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$? Jul 21, 2015 at 23:52

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.
• 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$. May 28, 2014 at 16:43
• 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! May 28, 2014 at 21:42