On $F_k$-free extermal graphs

Question

In 1995, Erdos, Furedi, Gould and Gunderson considered the Turan-type problem for $F_k$-free graphs, and they established the following result:

For $k\geq 1$ and $n\geq 50k^2$, we have ‎$$ ex(n,F_k )=‎\lfloor ‎‎\frac{n^2}{4}‎‎ ‎\rfloor + ‎‎ ‎\begin{cases}‎‎ k^2 -k, & \text{if k is odd;}‎\\‎ k^2 ‎-‎\frac{3}{2}k, &‎ ‎\text{if k is even}.‎ ‎\end{cases}‎ ‎$$ Furthermore, the number of edges is best possible. If $k\; (n \geq 4k −1)$ is odd, then the unique extremal graph is constructed by taking a complete equi-bipartite graph and embedding two vertex disjoint copies of $K_k$ in one side; if $k\; (n \geq 4k − 3)$ is even, then the extremal graph is constructed by taking a complete equi-bipartite graph and embedding a graph with $2k −1$ vertices, $k^2 − \frac{3k}{2}$ edges and maximum degree $k −1$ in one side.

Here $F_k$ denotes the $k$-fan consisting of $k$ triangles which intersect in exactly one common vertex.

I don't understand how to construct and to plot the shape of the extermal graphs explained above. Is there anyone who plots two graphs (for two cases of $k$: odd and even) for me to understand them?

Thanks in advance.

Answer 1

Here's an example of the construction when $k=3$, with the two copies of $K_3$ highlighted in red:

In this example $n=20$, so we start with $K_{10,10}$ and add the two copies of $K_3$. If $n$ were odd, we would start with a slightly unbalanced bipartite graph: for example, for $n=21$, we would start with $K_{10,11}$. In that case, the two copies of $K_3$ can be added on either side (but both on the same side).

---

Here's an example of the construction when $k=4$, with the added edges highlighted in red:

There are many options for the red subgraph: when $k=4$, we are looking for a graph with $7$ vertices, $10$ edges, and maximum degree $3$.

In general, the value $k^2 - \frac32 k$ is simply the most edges a graph with $2k-1$ vertices and maximum degree $k-1$ can have. Such a graph will have degree sequence $$\underbrace{k-1, k-1, \dots, k-1}_{2k-2 \text{ times}}, k-2.$$ Not all the degrees can be $k-1$, because that would be an odd number of odd degrees.

---

Technically speaking, it is not correct to say that the extremal graph is unique, merely that it is always a graph that matches the description given. There are two places where we have the flexibility to get multiple extremal graphs:

1. Whenever $n$ is odd, we start with a bipartite graph with parts of size $\frac{n-1}{2}$ and $\frac{n+1}{2}$. The extra edges we add can be put in either part, which does not produce isomorphic graphs.
2. Whenever $k$ is even (and at least $4$), there are many non-isomorphic graphs with the degree sequence $k-1,k-1,\dots,k-1,k-2$, and we can add any of them to get a valid extremal example.

Only when $k$ is odd and $n$ is even do we get a unique extremal graph (or if $k$ is odd and $n=4k-1$, since then we are adding two copies of $K_k$ to $K_{2k,2k-1}$, and only the side with $2k$ vertices is big enough to fit them).