# Connected planar graph with $n \geq 4$ vertices and $m$ edges, all edges in a cycle and no 2 3-cycles share an edge: show $m \leq \frac{12}{5}(n-2)$

This was a question I came across whilst revising for a graph theory exam. I cannot see a way to begin tackling this problem.

Thus far I have tried to go along the lines of the proof for the general bound of $$m \leq 3n-6$$ where most proofs uses a cycle counting method:

Each face corresponds to a cycle, and let $$e(F_i)$$ denote the number of edges surrounding the face $$F_i$$. If counting each bridge twice we have then $$\Sigma F_i = 2m$$ - after which we can then make use of the fact that each cycle must have length $$\geq 3$$ and Euler's formula to get the bound.

The above proof involves observing an inequality for each face, and I thought I would try to find a similar inequality for each face here. However, so far I couldn't see any (apart from trivial inequalities that don't get nearly as a tight bound) feasible inequalities that may help derive this bound. I believe the main difficulty is that the bound would need to involve multiple faces.

Thank you very much for reading through my question.

• Try with $n=4$ and see what is the maximum $m$. Then $n=5$. See if you can apply induction on $n$. Feb 14, 2019 at 18:12
• @rtybase Hi, thank you for the suggestion. I tried for a while afterwards and I couldn't seem to be able to get the induction to work. I think we need to at some point in the induction delete a vertex to use the induction hypothesis, however I can't see a way to find a good vertex to delete without breaking some of the question assumptions. (BTW I have edited the question to include a condition I forgot to mention - every edge of the graph belongs in a cycle). Feb 14, 2019 at 21:26

I've managed to figure it out a few days later:

Suppose $$G$$ has $$n$$ vertices, $$m$$ edges and $$f$$ faces. No two triangles shares an edge means that any 2 triangles must be edge-disjoint. This means the number of triangles in $$G$$ must be bounded by $$m/3$$, as each triangle will take up 3 edges since no edges may be shared. Let the number of triangles in $$G$$ be $$x$$ (so $$0 \leq x \leq m/3$$), and let $$e(F)$$ denote the number of edges surrounding the face $$F$$. We may obtain the following inequality:

$$2m = \sum_{F_i\ is\ a\ face} e(F_i) = \sum_{F_i\ is\ a\ triangle} e(F_i) + \sum_{F_j\ has\ \geq\ 4\ edges} e(F_j) \geq 3x + 4(f-x)$$

$$\therefore f \geq m/2+x/4$$

Subbing into the Euler identity for planar graphs, $$n+f-m=2$$, we get:

$$n + \frac{x}{4} - \frac{m}{2} \geq 2 \implies 2(n-2) \geq m - \frac{x}{2}$$

Using the fact that $$0 \leq x \leq m/3$$, we see the inequality is tightest for $$m$$ at $$x = m/3$$. So we have:

$$2(n-2) \geq 5m/6 \implies \frac{12}{5}(n-2) \geq m.\ \square$$