Recently I was thinking about a question:
- what is the upper bound on the number of four cycles for 3-connected quadrangulation graphs with $n$ vertices?
I use the plantri software, and propose the following conjecture.
Conjecture: The maximum number of $C_4$ in a 3-connected quadrangulation graph $G$ with $n$ vertices is given by
$$ \begin{cases} 6 & n=8\\ 8& n=10\\ 2n-13& m\ge 11 \end{cases} $$
Since 3-connected quadrangulation graph class seems to have a good recursive structure, mathematical induction may be useful. Some of my thoughts are as follows：
- If there is no separating 4-cycle in $G$, then the number of 4-cycles is equal to the number of 4 faces of $G$ which is $n-2$.
- If there is a separating cycle $C$ in the graph. Let $C_{int}$ be the all inner vertices of $C$ and $C_{out}$ be all outer vertices of $C$. Now I have difficulty in proving it. For example, I can't deal with a situation that the induced subgraph $G[V(C)\cup V(C_{int})]$ is isomorphic to a cube graph. Here we want to make inductive assumptions about subgraphs $G[V(C)\cup V(C_{out})]$ , but the problem is that $G[V(C)\cup V(C_{out})]$ is not necessarily 3-connected. We can't use induction here.
I don't know if someone solved this problem in some paper or if it's just a simple exercise. I don't know yet.
I post a related problem in MathOverflow: Is there any study on the bounds on the number of even cycles for planar bipartite graphs?