1
$\begingroup$

I'm trying to calculate the maximum number of edges in a planar graph without cycles of length $3$ and $4$ (thus, $C_3$ and $C_4$). I've assumed that the condition is that the length of each face has to be at least $5$.

I've written that $2m \leq 5f$ (m - number of edges, f - number of faces) and then I've used Euler's formula for faces, $f=m-n+2$. At the end I got that $3m \leq 5n-10$ is the maximum number of edges that a planar graph can have if it doesn't have a cycles of length 3 and 4.

Is this correct? Am I doing something wrong? Could someone please comment?

$\endgroup$
2
$\begingroup$

Looks fine to me. Note that it shows Petersen is not planar and is tight for the dodecahedron, as it should be.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.