# If $G$ is any n-vertex triangle free graph not containing a copy of $D_d$, then $e(G) \leq n(d-1)$

when revising for an upcoming exam on Graph Theory I came across the problem above. This was the last part to a question on Extremal Graph Theory, and in the previous parts, the question covered the Erdos-Stone Theorem, for the special case of $$r=3$$ and the Zarankiewski problem bound for bipartite graphs (Kővári–Sós–Turán theorem).

Here, $$D_d$$ is the unique tree with $$2d$$ vertices containing 2 adjacent vertices with degree $$d$$ ($$D_d$$ is the double star)

I observed that firstly $$G$$ being triangle free implies it does not contain a copy of $$K_3(1)$$. The bound $$e(G) \leq n(d-1)$$ is also similar to the bound of $$z(n,t) \leq (t-1)^{1/t}n^{2-1/t}+(t-1)n$$ for the Zarankiewski problem (I proved the bound of $$ex(2n, K_{t,t} \leq 2(t-1)^{1/t}n^{2-1/t} + 2(t-1)n$$ in an earlier part). Furthermore $$z(n,t)$$ is a bound concerning the extremal number of bipartite graphs, and since $$D_d$$ is bipartite it seems the bound shown earlier will see some use here. All of which does suspiciously point to the previous parts.

However despite of this I cannot see a way to solve this problem.

Suppose that $$G$$ is a triangle-free graph with $$n$$ vertices and at least $$n(d-1)$$ edges.
If there is a vertex $$v$$ of degree at most $$d-1$$, then $$G-v$$ is a triangle-free graph with $$n-1$$ vertices and at least $$(n-1)(d-1)$$ edges. By repeating this for as long as possible, we arrive at a triangle-free graph with $$k$$ vertices, at least $$k(d-1)$$ edges, and minimum degree $$d$$.
Now take any edge $$vw$$ together with $$d-1$$ more neighbors of $$v$$ and $$d-1$$ more neighbors of $$w$$; because the graph is triangle-free, none of those neighbors are common between $$v$$ and $$w$$, so we get a double star.