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



Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?
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.


