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.


1 Answer 1


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.

  • $\begingroup$ Now that is a really clever method! Thank you for your answer. I wonder if it is the same way that the examiner expected - for most of the question it seems to me that it was leading me down the path of using those inequalities proved prior. $\endgroup$
    – CowNorris
    Apr 3, 2019 at 21:34
  • $\begingroup$ I assume it was the intended solution. The trick of forcing minimum degree is standard - and if you can do it, you lose nothing by doing it, so you might as well always do it whenever you can. $\endgroup$ Apr 3, 2019 at 21:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .