On a lemma for planar graphs

141 Views Asked by At

Throughout, let $G$ be a planar graph with $n$ vertices, $e$ edges and $f$ faces. Additionally, let $n_k$ be the number of vertices of degree $k$ and $f_k$ be the number of faces with $k$ edges. I have come across a simple lemma that would make a nice exercise. Has anyone seen this before?

Lemma: Let $G$ be a planar graph with every vertex of degree at least 3 so that no triangles share an edge (equivalently, $G$ does not contain a diamond as a subgraph). Then $f_3 < 2f/3$.

Lemma: (Dual version) Let $G = (V,E)$ be a graph with $f_1=f_2=0$ such that no two degree 3 vertices are incident. Then $n_3 < 2n/3$.

Proof: Let $e_3$ be the number of edges contained in a triangle and $e'$ be the number of edges that are not. Since no edge is contained in two triangles, we see $e_3 + e' = e$ and $3f_3 = e_3$.

Since every vertex has degree at least three, $$ 2e = \sum_{v \in V} deg(v) = \sum_{k \geq 3} k \cdot n_k \geq 3 n_3 + 4(n-n_3). $$ Rearranging, we have $n_3 \geq 4n - 2e$.

Let $v$ be a vertex of degree $3$. Since no edge is contained in two triangles, at least of the edges containing $v$ is not part of a triangle, so contributes to $e'$. That edge may contain two vertices of degree $3$, so we have $n_3 \leq 2e'$.

Combining these observations, we have $$ f_3 = \frac{e_3}{3} = \frac{e - e'}{3} \leq \frac{e - n_3/2}{3} \leq \frac{2e - 2n}{3} = \frac{2f-4}{3} < 2f/3 $$ where the final equality is Euler's formula.

I would be interested in an explicit reference or better proof of this lemma. In particular, I don't understand why I should have to analyze degree three vertices -- it seems like a direct argument that does not reference degrees at all should be possible.