Skip to main content
2 of 2
edited body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Every $n$-vertex planar graph has at most $O(n^k)$ copies of $C_{2k}$. Note that the bipartite assumption is not needed. A more general result is proven in my paper Subgraph densities in a surface with Gwenaël Joret and David Wood, where we prove that the same bound holds for graphs embeddable in any fixed surface. In fact, we determine the maximum number of copies of $H$ in an $n$-vertex graph embeddable in a surface of Euler genus $g$, for every fixed graph $H$ (up to a multiplicative constant).

There is a matching lowerbound, and in the case of an even cycle, the construction is bipartite. Thus, the answer to your question is $\Theta(n^k)$ for $C_{2k}$. For the construction, take $C_{2k}$ and blow-up every other vertex into a stable set of size around $n/k$. This is a bipartite planar graph with $\Omega(n^k)$ copies of $C_{2k}$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187