2
$\begingroup$

Here's what I've got so far. I'm stuck on how to proceed. I believe I need to plug back into Euler's formula, but I'm not getting what I'm looking for by doing that. Where is the denominator of $3$ coming from in the result? Can you please check over my proof for any incorrect statements, and help me move forward?

Proof. Let $G$ be a connected planar graph with at least two edges, and a cycle with length $\ge 8$. Pick a crossing-free embedding of $G$; this embedding has $f$ faces. By Euler's formula, $$f = 2 - |V| + |E|\;.$$ We calculate the sum of the degrees of the faces in this embedding. On the one hand, the sum of the face degrees is $2|E|$ by proposition. On the other hand, since there is a cycle of at least length $8$, the sum of the face degrees is at least $8f$.

That's where I'm stuck at. Any ideas?

$\endgroup$
4
$\begingroup$

If every cycle has length at least eight, then every face in your crossing-free embedding is bounded by at least eight edges, so $8f < 2|E|$, or simply $4f < |E|$. Combining this with Euler's characteristic formula, $$\begin{align} |E|=f+|V|-2 &\implies 4|E| = 4f + 4|V| - 8 \\ &\implies 4|E| \leq |E| + 4|V| - 8 \\ &\implies 3|E| \leq 4|V| - 8 \\\\ &\implies |E| \leq \frac{4}{3}|V| - \frac{8}{3} \\ \end{align}$$

$\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.