# Planar graph, Minimum degree of a vertex at least 3 and Number of faces of a graph

Lemma: Suppose that a plane simple graph on $$n ≥ 4$$ vertices with the minimal degree of a vertex at least $$3$$ does not have faces of degree $$4$$ or $$5$$. Prove that there are at least $$4$$ faces of degree $$3$$ (triangles) in this graph.

I saw that a similar question was asked by Dolva Planar graph, number of faces, minimum vertex degree 3. Where the Handshaking lemma and Euler's formula $$v-e+f=2$$ were suggested. But I am still stuck.

• @kabenyuk I actually drew a graph using n=4 satisfying the given condition but it is not containing 4 faces of degree 3.
– Logo
May 3, 2021 at 17:36
• @Kabenyuk could please explain in details how you got proved it
– Logo
May 3, 2021 at 17:36
• @Violet It would be interesting to look at your drawing. Note that this is not a proof, just hints. May 4, 2021 at 9:48
• @kabenyuk yeah I understood what I did wrong....I forgot to consider the outer region face and how to calculate it's degree....
– Logo
May 4, 2021 at 12:19
• That's what I thought. May 6, 2021 at 6:54

1. $$v\leq2e/3$$;
2. $$3k+6(f-k)\leq2e$$, $$k\leq3$$, then $$f\leq e/3+k/2$$;
3. $$2=v-e+f\leq 2e/3-e+e/3+k/2=k/2\leq3/2$$.
• Let $V$ be the vertex set of our graph. Since $\sum_{u\in V}{\rm deg}(u)=2e$ and ${\rm deg}(u)\geq3$ for each vertex $u$ of $V$, it follows that $v\leq2e/3$. Let $\cal F$ denote the set of all faces and $k$ denotes the number of faces of degree 3. Since $\sum_{F\in\cal F}d(F)=2e$ and $d(F)\geq6$ or $d(F)=3$, it follows that $f\leq e/3+k/2$. May 4, 2021 at 3:59