Let $F$ be the butterfly graph. Show that $ex(n, F)=\lfloor{\frac{n^2}{4}}\rfloor+1$.

Question

$ex(n, F)$ is the maximum number of edges in an $n$-vertex $F$-free graph, and is called extremal number of $F$. Showing $ex(n, F)\geq \lfloor{\frac{n^2}{4}}\rfloor+1$, can be justified by taking a balanced $n$-vertex complete bipartite graph and adding only one edge in one of the two partition class. To show the upper bound, I started by assuming there is an $F$-free graph with size more than $\lfloor{\frac{n^2}{4}}\rfloor+1$ edges and from this it can be shown that the graph contains two triangles sharing an edge. How can I reach on contradiction from this point? Or is there some other short proof to justify the upper bound?

Answer 1

This is a long comment rather than an answer.

Try to prove that bowtie-free (or butterfly-free) graph $G$ of order $n\geq5$ has at most $[n^2/4]+1$ edges by the following plan.

1. Prove from the contrary that there exists a vertex $v\in V(G)$ that $\operatorname{deg}(v)\leq[n/2]$.

2. Let $v\in V(G)$ be a vertex of minimum degree. Given (1) the degree of $v$ is not greater than $[n/2]$.

3. Let $H=G-v$. The graph $H$ is also bowtie-free graph. By induction $|E(H)|\leq[(n-1)^2/4]+1$.

4. We have $|E(G)|=|E(H)|+\operatorname{deg}(v)$. Next we use (2) and (3).

It seems to me that we can get our result on this way.