Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to get (upper and lower) bounds on the number of 4-cycles($K_{2,2}$) in planar 3-regular bipartite graphs. The best I have been able to get is a bound based on the Euler characteristic. I know the upper bounds should be better than for general bipartite graphs due to the utility graph being a forbidden minor. The planarity and 3-regularity seem to also impose a lower bound.

For a graph as above with $2n$ vertices and $3n$ edges, I have gotten so far that there must be at least $\frac{n}{2}+4$ square faces in the graph by using the Euler characteristic. Are there such graphs where the faces are the only 4-cycles? It seems like a better bound should be possible.

Also I have come up with a construction for a planar bipartite graph (not cubic) that has at least $4n+2$ four-cycles. But since it isn't cubic, and I am not sure if it is tight anyway, I don't see how it helps me.

If there are known results, those would be welcome, but I would really like to learn how to prove the bounds for this on my own. With that in mind even hints are acceptable.


Okay, I think there are some fishy numbers in the comments, so I am going to show my work. We are assuming connected graphs.

Three regular graphs have an even number of vertices, and every bipartite cubic graph has a Tait coloring of the edges. This implies for a graph on $2n$ vertices, there are precisely $n$ in each side of the bipartition. By the handshaking lemma, there are $3n$ edges. Thus, Euler's characteristic implies that there are precisely $n+2$ faces, none of which are triangles. This should imply based on dtldarek's comment, that there are at most $n+2$ 4-cycles. But that can't be true (that for triangle free planar graphs all 4-cycles are faces), because of the following bipartite planar graph:


It has 4 faces, but 5 distinct four-cycles.

I will post my lower bound derivation when I get a chance.

share|cite|improve this question
The cube is a planar cubic graph that has $2\cdot 4$ vertices, $3\cdot 4$ edges and $4/2+4$ square faces (each face is a square). – dtldarek Jan 20 '14 at 12:31
I'm only saying that any bounds have to admit that example. On the other hand, the cube seems saturated with squares, i.e. it should be easy to construct a graph with smaller number of squares per vertex (e.g. this). I'm not sure I follow which bounds you call lower and which upper. – dtldarek Jan 20 '14 at 12:59
@dtldarek yes sorry, correct. I will fix it. By lower bound I mean the minimum number of cycles possible and by upper bound I mean the maximum number of cycles. both parameterized by half the number of vertices . – Tim Seguine Jan 20 '14 at 13:02
@dtldarek Now you have me wondering where I made a mistake. Would it help if I posted my derivation? – Tim Seguine Jan 20 '14 at 13:06
@dtldarek okay. I only reversed the inequality sign then probably. I will look over my work again. – Tim Seguine Jan 20 '14 at 13:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.