1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Try with $n=4$ and see what is the maximum $m$. Then $n=5$. See if you can apply induction on $n$. $\endgroup$
    – rtybase
    Feb 14, 2019 at 18:12
  • $\begingroup$ @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). $\endgroup$
    – CowNorris
    Feb 14, 2019 at 21:26

1 Answer 1

1
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .