A stability theorem on fractional covering of triangles by edges

Let ν(G)ν(G) denote the maximum number of edge-disjoint triangles in a graph GG and τ∗(G)τ∗(G) denote the minimum total weight of a fractional covering of its triangles by edges. Krivelevich proved that τ∗(G)≤2ν(G)τ∗(G)≤2ν(G) for every graph GG. This is sharp, since for the complete graph K4K4 we have ν(K4)=1ν(K4)=1 and τ∗(K4)=2τ∗(K4)=2. We refine this result by showing that if a graph GG has τ∗(G)≥2ν(G)−xτ∗(G)≥2ν(G)−x, then GG contains ν(G)−⌊10x⌋ν(G)−⌊10x⌋ edge-disjoint K4K4-subgraphs plus an additional ⌊10x⌋⌊10x⌋ edge-disjoint triangles. Note that just these K4K4’s and triangles witness that τ∗(G)≥2ν(G)−⌊10x⌋τ∗(G)≥2ν(G)−⌊10x⌋. Our proof also yields that τ∗(G)≤1.8ν(G)τ∗(G)≤1.8ν(G) for each K4K4-free graph GG. In contrast, we show that for each ϵ>0ϵ>0, there exists a K4K4-free graph GϵGϵ such that τ(Gϵ)>(2−ϵ)ν(Gϵ)τ(Gϵ)>(2−ϵ)ν(Gϵ).