Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

EDIT

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:

counterexample

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

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

share|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 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 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 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 at 13:06
    
@dtldarek okay. I only reversed the inequality sign then probably. I will look over my work again. –  Tim Seguine Jan 20 at 13:11

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.